Компьютерная игра (платформы)

@newyork7776 · Регистрация: 21.05.2013

Студворк — интернет-сервис помощи студентам

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

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

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

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

Примеры тестов
входные данные
3
1 5 10
выходные данные
9

входные данные
3
1 5 2
выходные данные
3

Добавлено через 1 минуту

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
    vector <int> v;
    vector <int> q;
    int s=0,n,k,rez=0;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
    rez=0;
    for(int i=2;i<n;i++)
    {
        if ((v[i-1]+v[i-1])>(v[i]))
            {
                rez+=v[i];
            }
        if ((v[i-1]+v[i-1])<=(v[i]))
            {
                rez+=(v[i-1]+v[i-1]);
            }
    }
    cout << rez << "\n";
    system("pause");
}

вот моя пародия на код

@Folko · 10.11.2013, 00:26

newyork7776, а почему пародия? Не работает?

@nokados · 10.11.2013, 00:28

Сообщение от newyork7776

1 ≤ n

Если (n==1) 0 печатать?

@Kuzia domovenok · 10.11.2013, 00:29

На acmp.ru есть похожие задачи. Можешь спросить там!

@newyork7776 · 10.11.2013, 00:30 **[ТС]**

Сообщение от Folko

newyork7776, а почему пародия? Не работает?

пашет но ответ кривой

@nokados · 10.11.2013, 01:32

Я решил. Вот код с комментариями <КЭП> :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
 
void main()
{
    
    //Инициализация переменных
    int n;//колличество платформ
    cin>>n;//Ввод
    int* CoordsY = new int[n];//Массив с координатами платформ
    int* MinE = new int[n];//Массив с минимальными энергозатратами от начала до платформы
 
    //Ввод
    for(int i=0; i<n;i++)
        cin>>CoordsY[i];
 
    MinE[0]=0;//От начала до начала энергия не потратится
    MinE[1]=abs(CoordsY[1]-CoordsY[0]);//Здесь тоже однозначно
 
    int E1,E2;//Затраты энергиив при разных случаях
    for (int i=2;i<n;i++)//Найдем все остальные
    {
        E1=abs(CoordsY[i]-CoordsY[i-1]); //Энергия при обычном прыжке
        E2=3*abs(CoordsY[i]-CoordsY[i-2]); //Энергия при СУПЕР-прыжке
 
        //Найдем минимальную энергию, которую может затратить игрок
        if (E1+MinE[i-1]<E2+MinE[i-2])// Если выгоднее прыгнуть с ближайшей, то
            MinE[i]=E1+MinE[i-1];//прыгаем с ближайшей
        else // а если выгоднее прыгуть с дальней
            MinE[i]=E2+MinE[i-2];//то прыгаем с дальней
    }
 
    //Вывод
    cout<<MinE[n-1];
 
    system("pause >> void");
}

@newyork7776 · 10.11.2013, 12:59 **[ТС]**

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
 
int step(int a,int b,int c)
{
    if ((abs(a-b))>=(3*abs(a-c))) return (3*(abs(a-c)));
    else return (abs(a-b));
}
 
int main()
{
   vector <int> v;
   int q=2,n,k;
   cout << "Enter N = ";cin >> n;
   for(int i=0;i<n;i++)
   {
        cin >> k;
        v.push_back(k);
   }
   int rez=0;
   while (q==n)
   {
       if ((step(v[q],v[q-1],v[q-2])) == (3*(abs(v[q]-v[q-2]))))
       {
           q+=2;
           rez+=(3*abs(v[q]-v[q-2]));
       }
       else 
       {
           q++;
           rez+=abs(v[q]-v[q-1]);
       }
   }
    cout << rez;
    system("pause");
}

может я не понимаю основу идею,но делаю примерно так ,где я ошибся?

@nokados · 11.11.2013, 00:41

1) почему

C++
1
while (q==n)

??

2)Чтобы правильно оценивать, с какой платформы нужно прыгать, нужно знать не только, сколько энергии затратится, но и сколько энергии уже затратилось. Другими словами, когда выбираешь лучший путь, минимальная энергия будет равна min(E_{от дальней}+E_{от начала до дальней}, E_{от ближней}+E_{от начала до ближней})
где E_{от дальней} равна (3*abs(a-c), а E_{от начала до дальней} равно минимальной энергии от начала до этой платформы. Ее значение можно хранить в дополнительно массиве, созданном специально для хранения минимальных энергозатрат. Именно поэтому важно также находить минимальное расстояние от начала до каждой платформы, то есть использовать q++
Попробуй разобрать пример с вводимыми числами: 1 5 2 5

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Folko 267 / 255 / 27 Регистрация: 27.09.2013 Сообщений: 876 Записей в блоге: 1
	10.11.2013, 00:26
	newyork7776, а почему пародия? Не работает? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,536 Записей в блоге: 1
	10.11.2013, 00:29
	На acmp.ru есть похожие задачи. Можешь спросить там! 0