Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? если да, то может быть вы и сами не знакомы с этим развлечением? впрочем, трудностей при решении этой это создать не должно. во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. он должен перебраться от одного края экрана до другого. при этом при прыжке с одной платформы на соседнюю, у героя уходит |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
Ответы на вопрос:
//у меня прошел все тесты
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;
int abc(int a)
{
if(a > 0)
return a;
return a *= -1;
}
int main()
{
int n;
cin> > n;
vector< int> d(n+1);
//ввод
for(int i = 1; i< =n; i++)
{
cin> > d[i];
}
vector< int> b(n+1);
b[1] = d[1];
b[2] = abc(d[2] - d[1]);
//дп
for(int i = 3; i< =n; i++)
{
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;
if(i == 3 & & b[i] == z)
{
b[i] -= d[i-2];
}
}
cout< < b[n]< < endl
}
Популярно: Информатика
-
vorontsovaksus16.03.2021 08:23
-
WANNNO08.04.2021 02:10
-
Marinap04174405.07.2022 20:06
-
Alesha211206.01.2020 20:33
-
polyakkate01.12.2020 16:01
-
73Женя9102.01.2021 11:32
-
kkkddd9022.10.2022 09:48
-
Ник111111н05.05.2023 06:53
-
RILIR07.03.2022 11:56
-
лика2004225.12.2021 03:38