Как решить задачу про кузнечика путем динамического программирования?

Question

[xxxx_videos]

По условию есть какое то количество кувшинок с разным количеством травы на каждой. оно может быть положительным и отрицательным. кузнечик изначально стоит на первой кувшинке, а прыгать может только либо через одну кувшинку, либо через две. нужно найти максимальное количество травы которую соберет кузнечик по пути к последней кувшинке.
на вход дается число n(количество кувшинок), и n разных чисел(количество травы на кувшинках). вывести нужно максимальное количество.
На одном из тестов программа выдает неправильный ответ. Какие там входные данные я не знаю, поэтому не могу понять что не так. помогите найти ошибку

#include <iostream>
using namespace std;

int max(int one, int two)
{
    if (one > two)
        return one;
    return two;
}

int main()
{

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int N;
    int a[1000];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> a[i];
    a[2] = a[0] + a[2];
    a[3] = a[0] + a[3];
    a[4] = a[2] + a[4];
    for (int i = 5; i < N; i++)
        a[i] += max(a[i - 2], a[i - 3]);
    cout << a[N - 1];
}

Comments

[Akina]

1) Может ли он прыгать назад?
2) Может ли он завершить сбор на середине?

[xxxx_videos]

Akina, может прыгать только вперёд. Завершить надо на последней кувшинке.

[Alexandroppolus]

1000 элементов точно хватает?

[xxxx_videos]

Alexandroppolus, на тесте где ошибка 1000 не хватает, если 1000 то выдаёт runtime error, я пробовал делать массив на максимальное количество элементов в задаче 100000, тогда уже выдаёт wrong answer. В общем на тесте где много кувшинок почему то не работает

[Alexandroppolus]

xxxx_videos,

максимальное количество элементов в задаче 100000

так понятно что с массивом на 1000 будет с багами.

сделай динамическое выделение памяти
int *a = new int[N];
вроде так, если не ошибаюсь

[Alexandroppolus]

либо глобальную переменную
int a[100000];

[xxxx_videos]

Alexandroppolus, да не, я просто сюда выложил с массивом на 1000, на сайт тестирующий я загружал код с массивом 100000. Ошибка именно в ответе который выводится.

Answer 1

[Alexandroppolus]

Кузнечику обязательно побывать на последней кувшинке?
Если нет (если можно её проскочить), то сделай в конце cout << max(a[N-2], a[N - 1]);

Comments

[xxxx_videos]

надо добраться до последней кувшинки.

Answer 2

[Wataru]

Опишите ваше динамическое программирование - физический смысл функции и рекуррентное соотношение.

Comments

[xxxx_videos]

a[i]=max(a[i-2],a[i-3]) + a[i]. это формула что бы найти максимальную сумму для каждой кувшинки

[Wataru]

xxxx_videos, вы сформулируйте для себя хотя бы. F(k) - это максимальное количество травы, которое можно собрать, если... Если что означает k?

[Wataru]

xxxx_videos, Короче, наверняка там переполнение. Уточните ограничения в задаче. Может быть сумма в int не помещается. Плюс проверьте крайние случаи. Что у вас выводится при N <=5? Что вообще выводить надо, если N=2, ведь на последнюю кувшинку никак не запрыгнуть?

[xxxx_videos]

Wataru, я пробовал учитывать эти случаи, все равно выдает неправильный ответ на одном и том же тесте.

[Wataru]

xxxx_videos, Какие ограничения в задаче? Насколько большие числа могут быть? Чему может быть равно N?