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

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #5649
      @admin
      StudLance.ru

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

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

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

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

      Входные данные

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

      Выходные данные

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

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 3
      1 5 10
      9
      2 3
      1 5 2
      3

      Разбор решения задачи

      Эта задач очень похожа на другую, разобранную нами в качестве примера на тему «Динамическое программирование».

      На этот раз от нас требуют найти минимальную стоимость прохождения по платформам. При этом есть добраться до любой платформы можно двумя способами:

      $$
      f_{simple}(n) = f(n-1) + d(n-1, n) \\
      f_{super}(n) = f(n-2) + d(n-2, n) \cdot 3 \\
      f(n) = min(f_{simple}(n), f_{super}(n))
      $$

      Тут f(n) — минимальная стоимость попадания на платформу с номером n, d(a, b) — расстояние между платформами a и b.

      Видно, что для вычисления f(n) нам нужно вычислить f(n-1) и f(n-2), попробуем сделать это рекурсивно:

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      int min_energy(const vector<int>& platforms, size_t pos) {
        if (pos == 0)
          return 0;
      
        auto simple_step = abs(platforms[pos] - platforms[pos-1]) + min_energy(platforms, pos-1);
      
        if (pos == 1)
          return simple_step;
      
        auto super_step = abs(platforms[pos] - platforms[pos-2])*3 + min_energy(platforms, pos-2);
      
        return min(simple_step, super_step);
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
        ifst >> n;
      
        vector<int> plantforms(n);
        for (size_t i = 0; i < n; ++i)
          ifst >> plantforms[i];
      
        ofst << min_energy(plantforms, plantforms.size()-1);
      }

      Мы начинаем с последней платформы — f(n), нам нужны f(n-1) и f(n-2). Они вычисляются рекурсивно:

      f(n) <- f(n-1), f(n-2)
      f(n-1) <- f(n-2), f(n-3)
      f(n-2) <- f(n-3), f(n-4)
      f(n-3) <- f(n-4), f(n-5)
      ...

      Это очень простое решение и оно прекрасно работает для небольшого числа платформ. В самом деле, обратите внимание, что f(n-2), f(n-3) и все остальные значения платформ нам потребуются дважды. Однако, каждое обращение к ним будет приводить к вызову функции и объемным вычислениям.

      На картинке показаны зависимости по данным для платформ с номерами k+1, k+2 и k+3. Dидно, что процесс поиска по-сути линейный, однако наша функция каждый раз производит вычисления заново, т.е. работает примерно так:

      Она работает не в 2 раза медленее, а примерно в 2^n — обратите внимание, что f(k) для обработки трех последних платформ будет вызван уже трижды.

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

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      struct Platform {
        int height;
        bool ready;
        int min_energy;
      
        Platform()
          : height(0), ready(false), min_energy(-1) {
        }
      };
      
      int d(const Platform& a, const Platform& b) {
         return abs(a.height - b.height);
      }
      
      int min_energy(vector<Platform>& platforms, size_t pos) {
        if (pos == 0)
          return 0;
      
        if (platforms[pos].ready)
          return platforms[pos].min_energy;
      
        auto simple_step = d(platforms[pos], platforms[pos-1]) + min_energy(platforms, pos-1);
      
        if (pos == 1)
          return simple_step;
      
        auto super_step = d(platforms[pos], platforms[pos-2])*3 + min_energy(platforms, pos-2);
      
        platforms[pos].min_energy = min(simple_step, super_step);
        platforms[pos].ready = true;
      
        return platforms[pos].min_energy;
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
        ifst >> n;
      
        vector<Platform> plantforms(n);
      
        for (size_t i = 0; i < n; ++i) {
          ifst >> plantforms[i].height;
        }
      
        ofst << min_energy(plantforms, plantforms.size()-1);
      }

      В этом и заключается суть динамического программирования — вместо повторного вычисления мы проверяем «было ли это вычисленно раньше» и «если да» — берем готовые данные:

      if (platforms[pos].ready)
          return platforms[pos].min_energy;

      Однако, если мы пришли к линейному процессу вычисления, то зачем нам рекурсия? — Мы вполне можем обойтись циклом если будем обрабатывать не с последней платформы, а с первой. То есть, мы знаем, что стоимость попадания на первую платформу равна нулю, на вторую мы можем попасть только одним способом. Для третьей платформы — нам потребуются данные (уже готовые) от первух двух платформ:

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      struct Platform {
        int height;
        int min_energy;
      
        Platform()
          : height(0), min_energy(-1) {
        }
      };
      
      int d(const Platform& a, const Platform& b) {
         return abs(a.height - b.height);
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
        ifst >> n;
      
        vector<Platform> plantforms(n);
        for (size_t i = 0; i < n; ++i)
          ifst >> plantforms[i].height;
      
        plantforms[0].min_energy = 0;
        plantforms[1].min_energy = d(plantforms[1], plantforms[0]);
      
        for(int i = 2; i < n; ++i) {
          auto simple_step = d(plantforms[i], plantforms[i-1]) + plantforms[i-1].min_energy;
          auto super_step = d(plantforms[i], plantforms[i-2])*3 + plantforms[i-2].min_energy;
          plantforms[i].min_energy = min(simple_step, super_step);
        }
      
        ofst << plantforms[n-1].min_energy;
      }

      Последние два решения являются наиболее хорошими с точки зрения чистоты кода — алгоритм хорошо читается. Однако, мы можем уменьшить объем потребляемой памяти. Посмотрите еще раз на рисунок — для обработки i-той платформы нужны данные только двух предыдущих, а не всех, значит и хранить достаточно только два последних числа (вместо n):

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      int d(int a, int b) {
        return abs(a-b);
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
        ifst >> n;
      
        vector<int> plantforms(n);
        for (size_t i = 0; i < n; ++i)
          ifst >> plantforms[i];
      
        if (n == 1) {
          ofst << 0;
          return 0;
        }
      
        int e_i_1 = 0, e_i = d(plantforms[1], plantforms[0]);
        for(int i = 2; i < n; ++i) {
          auto simple_step = d(plantforms[i], plantforms[i-1]) + e_i;
          auto super_step = d(plantforms[i], plantforms[i-2])*3 + e_i_1;
      
          e_i_1 = e_i;
          e_i = min(simple_step, super_step);
        }
      
        ofst << e_i;
      }
      

      Это решение тоже можно улучшить по памяти — в самом деле, зачем нам хранить информацию о высотах всех платформ, когда нужны лишь две последние?

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      struct Platform {
        int height;
        int min_energy;
      
        Platform()
          : height(0), min_energy(-1) {
        }
      };
      
      int d(const Platform& a, const Platform& b) {
         return abs(a.height - b.height);
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        if (n == 1) {
          ofst << 0;
          return 0;
        }
      
        Platform prevPlatform, curPlantform;
        ifst >> prevPlatform.height >> curPlantform.height;
      
        prevPlatform.min_energy = 0;
        curPlantform.min_energy = d(prevPlatform, curPlantform);
      
        for (int i = 2; i < n; ++i) {
          Platform nextPlanftorm;
          ifst >> nextPlanftorm.height;
      
          auto simple_step = d(nextPlanftorm, curPlantform) + curPlantform.min_energy;
          auto super_step = d(nextPlanftorm, prevPlatform)*3 + prevPlatform.min_energy;
      
          nextPlanftorm.min_energy = min(simple_step, super_step);
      
          prevPlatform = curPlantform;
          curPlantform = nextPlanftorm;
        }
      
        ofst << curPlantform.min_energy;
      }
      
      

      StudLance.ru

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