Разбор олимпиадной задачи — Компьютерная игра

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 нед., 4 дн. назад.

  • Автор
    Сообщения
  • #5649
    @admin

    Задача взята с acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 38%)

    Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно.

    Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y2-y1| единиц энергии, где y1 и y2 – высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприем, который позволяет перескочить через платформу, но на это затрачивается 3*|y3-y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

    Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?

    Входные данные:
    В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы.

    Выходные данные:
    В выходной файл OUTPUT.TXT запишите единственное число – минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя).

    Пример 1:
    INPUT.TXT: 3
    1 5 10
    OUTPUT.TXT : 9

    Пример 2:
    INPUT.TXT: 3
    1 5 2
    OUTPUT.TXT : 3

    Это типичная задача динамического программирования. Для расчета кратчайшего пути до платформы N необходимо расчитать кратчайшие пути до предыдущих платформ. Платформы представим в виде массива, заполнять который будем последовательно.

    Мы «встаём» на очередную платформу и смотрим какой путь до этой платформы будет самым
    оптимальным. Есть два варианта того, как мы доберёмся до этой платформы, на которой мы стоим: доберёмся обычным прыжком или суперпрыжком, перескочив предыдущую платформу. Для того чтобы понять какой прыжок необходимо использовать, нужно сравнить два возможных пути до платформы. Ниже процесс поиска оптимального пути провизуализирован:

    В каждой платформе находится 2 числа, первое – это высота платформы, а второе – количество энергии, затраченное для перемещения на данную платформу. Над каждой стрелкой отображается затраты энергии на прыжок.

    Рассмотрим данный пример. Путь до третьей платформы очевиден и ведёт к двум простым прыжкам. Для того чтобы добраться до 5 платформы
    необходимо либо с 3 платформы прыгнуть на 4, а потом на 5, либо с 3 сразу на 5. Рассчитаем кратчайший прыжок до 5 платформы: путь до 4 платформы + прыжок с 4 на 5 + прыжок с 5 на 6 или путь до 5 платформы + прыжок с 5 на 6. Итого: 2 + 5 + 3 = 10 больше 2 + 6 = 8. Таким образом видно, что суперпрыжок ведёт к кратчайшему пути до 5 платформы.

    Исходный код решения:

    #include <fstream>
    #include <vector>
    
    using namespace std;
    
    //elements - массив с платформами, где значение в векторе — это высота платформы
    int calculate(vector<int> elements) {
      const size_t n = elements.size();
      
      //количество затраченной энергии до каждой платформы
      vector<int> way(n);
      
      way[0] = 0;
      //Сразу прыгаем до второго элемента
      way[1] = abs(elements[1] - elements[0]);
    
      for (size_t i = 2; i < n; i++) {
        int jump = abs(elements[i] - elements[i - 1]);
        int superJump = abs(3 * (elements[i] - elements[i - 2]));
    
        //Добавляем прыжок к предыдущему пути
        jump += way[i - 1];
        superJump += way[i - 2];
    
        //Путь равен минимальному среди данных двух путей
        way[i] = min(jump, superJump);
      }
      
      //Возвращаем путь до последнего элемента
      return way[n - 1];
    }
    
    int main() {
      vector<int> platforms;
      ifstream ifst("input.txt");
      ofstream ofst("output.txt");
      size_t size;
    
      ifst >> size;
      platforms.resize(size);
    
      for (size_t i = 0; i < size; ++i) {
        ifst >> platforms[i];
      }
    
      ofst << calculate(platforms);
    }

Для ответа в этой теме необходимо авторизоваться.