Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в...

Question

Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно.
Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y2-y1| единиц энергии, где y1 и y2 – высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприем, который позволяет перескочить через платформу, но на это затрачивается 3*|y3-y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.
Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?
Входные данные
В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы.
Выходные данные
В выходной файл OUTPUT.TXT запишите единственное число – минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя).
INPUT.TXT
3
1 5 10
OUTPUT.TXT
9

Answer 1

//у меня прошел все тесты

#include

#include

#include

using namespace std;

int abc(int a)

{

   if(a > 0)

       return a;

   return a *= -1;

}

int main()

{

  int n;

   cin>>n;

   vector d(n+1);

//ввод

   for(int i = 1;i<=n;i++)</p>

   {

       cin>>d[i];

   }

   vector b(n+1);

   b[1] = d[1];

   b[2] = abc(d[2] - d[1]);

//дп

   for(int i = 3;i<=n;i++)</p>

   {

      long a = abc( d[i] -   d[i-1] );

       long z =  abc( 3 *  (  d[i]   -  d[i-2]  ) );

       a = a  + b[i-1];

       z =  z  + b[i-2];

       b[i] = min(a,z);

      // cout<<b[i]<<" "<<i<<endl;</p>

       if(i == 3 && b[i] == z)

       {

           b[i] -= d[i-2];

       }

  }

   cout<<b[n]<<endl</p>

}