Олимпиадная задача на ДП

Question

Прямо неудобно, но...

Малому задали домашку - выбрать и порешать любые задачки по ДП c e-olymp. Он выбрал среди прочих эту (текст ниже). Пришел ко мне через часик - что не так? Почему проходит только 22%?

Задача выглядит простейше, но чего-то я явно не вижу, потому что никаких ошибок (ну, кроме неоптимальности) в его коде, как по мне, нет. Ткните нас - что мы в упор не видим?...

Условие:

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

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

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

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

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

Выведите единственное число - минимальное количество энергии, которое должен потратить игрок на преодоление платформ.

Вот его решение:

#include <iostream>

using namespace std;

long long int m[100001];
long long int h[100001];

long long int sq(long long int n) { return n*n; }

long long int min(long long int x, long long int y) { return (x < y) ? x : y; }

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> h[i];
    }
    m[1] = 0;
    m[2] = sq(h[2]-h[1]);

    for(int i = 3; i <= n; ++i)
    {
        m[i] = min(sq(h[i]-h[i-1]) + m[i-1],
                   3*sq(h[i]-h[i-2]) + m[i-2]);
    }
    cout << m[n] << endl;
}

Ну, все просто - на первой платформе энергия 0, на второй - просто квадрат (попасть можно только с первой), дальше - смотрим затраты при обычном прыжке и суперпрыжке и берем минимальные... Диапазона long long int за глаза хватает.

Answer 1

Дело в том, что квадратичная функция "быстро" растет, поэтому герой иногда будет двигаться назад.

Пример

11 2 10 1
11-2-1=81+3=84
11-10-1 = 3+81 =84
11-10-2-1 = 3+64+3 =70

Пусть m[i] это минимум энергии 1->i.

Поставим m[1] = 0.

Если n=2, то на вторую мы можем попасть одним способом.

Если n>2, то двумя 1-2 или 1-3-2.

Теперь рассмотрим вычисление m[i].

Доступ к i-платформе можно получить с помощью (i - 1) или с помощью (i - 2), суперпeрудар.

Если i < n, то можно попасть на i-платформу с (i + 1), на которую вы перескочили с (i - 1).

m[i]=min из

m[i - 1] + |yi - yi-1|^2 : обычный переход с (i - 1) платформы;
m[i - 2] + 3 * |yi - yi-2|^2 : Суперудар с (i - 2) платформы;
m[i - 1] + 3 * |yi+1 - yi-1|^2 + |yi - yi+1|^2 : 1-3-2

Пример кода

#define MAX 100005

...
m[1] = 0;

if (n == 2)

  m[2] = sq(h[2] - h[1]);

else

  m[2] = min(sq(h[1] - h[2]), 3 * sq(h[1] - h[3]) + sq(h[2] - h[3]));


for(int i = 3; i <= n; i++)

{

  m[i] = min(m[i - 1] + sq(h[i - 1] - h[i]), 
                m[i - 2] + 3 * sq(h[i - 2] - h[i]));

  if (i < n)
     m[i] = min(m[i], m[i - 1] + 3 * sq(h[i - 1] - h[i + 1]) + sq(h[i] - h[i + 1]));

}

 cout <<  m[n];

БЛОГ НА HUSL

Олимпиадная задача на ДП

Ответы (1 шт):