Задача на динамическое программирование с Лягушкой
Имею задачу, которую не могу решить. Вроде задача выглядит как задача на ДП. Я ее так и решал.
int main() {
long long n; cin >> n;
vector<long long> kuv;
kuv.push_back(0);
for(long long i = 1; i < n + 1; i++){
kuv.push_back(0);
cin >> kuv[i];
// cerr << kuv[i] << " ";
}
// cerr << "\n" << n << " " << n +2 << " ----------\n";
long long x, y; cin >> x >> y;
vector<long long> te (n + 2, -1);
// cerr << "------------" << size(te) << " --------\n";
te[0] = 0;
for(long long i = 0; i < n + 2; i++){
for(long long j = i+x; ((j < (i + y)) && (j < n+1)); j++){
// cerr << i << " " << j << "\n";
// cerr << te[j] << " ";
// cerr << te[i] << " ";
// cerr << kuv[j] << "\n";
te[j] = max(te[j], te[i]+ kuv[j]);
}
}
/*
for(int i = 0; i < n+2; i++){
cout << te[i] << " ";
}
*/
cout << te[n];
return 0;
}
Но выдает TL. Ума не приложу где можно еще оптимизировать. Вот и сама задача:
Когда-то давно, в дремучем лесу, обитала особенная лягушка по имени Лягуш. Он обладал невероятной способностью — прыгать на целое число клеток вперед, но с ограничением: её прыжки могли быть длиной только от X X до Y Y клеток(обе границы - включительно). Лягуш мечтал покорить самый длинный и таинственный путь в лесу — от начальной точки до конечной.
Однажды Лягуш обнаружил перед собой длинный отрезок из N N клеток, каждая из которых содержала определенное число. Эти числа представляли собой таинственную карту, показывающую, какие награды могут ждать лягушку на каждом шагу. Лягуш понял, что для достижения своей мечты ему необходимо выбирать такой путь, который позволит ему набрать максимальную сумму сокровищ.
Так Лягуш и начал свой увлекательный путь. Изначально он стоял в клетке 0. Ему было важно не только добраться до конца, но и набрать наибольшую сумму на своем пути.
Прыгать назад нельзя. Длина прыжка - разность конечной и начальной координаты. Если Лягуш стоит в клетке 1, X X = 2, Y Y = 5, то за 1 прыжок можно оказаться в клетках 3, 4, 5, 6.
Формат ввода В первой строке вводится число N N ( 1 ≤ N ≤ 4 ∗ 1 0 5 1≤N≤4∗10 5 ) − − количество клеток на пути. Во второй строке через пробел вводятся числа a i a i ( 1 ≤ a i ≤ 1 0 9 1≤a i ≤10 9 ) − − количество сокровищ, которое получит Лягух, пройдя по этой клетке. В третьей строке через пробел вводится два числа X X и Y Y ( 10 ≤ X ≤ Y ≤ 1 0 5 10≤X≤Y≤10 5 ) − − минимальная и максимальная длина прыжка.
Формат вывода В единственной строке выведите максимальную сумму сокровищ, которую можно получить, дойдя от начальной клетки пути в конечную. Если до конечной точки допрыгать невозможно - вывести -1.
Пример 1 Ввод Вывод 10 6 2 2 2 8 3 9 1 2 1 10 100000 1 Пример 2 Ввод Вывод 11 5 6 4 7 6 2 9 7 2 2 7 12 13
Ответы (1 шт):
Ваш алгоритм получается квадратичным O(N*(Y-X)). Ограничения порядка 10^5 подразумевают, что потребуется лучшая сложность, в идеале линейная от N.
Чтобы этого добиться, можно использовать структуру данных "дек" (std::deque). Вектор te будет хранить лучшие результаты для каждой достигнутой позиции.
В деке хранятся индексы вектора te (можно пары индекс+значение), которые могут являться кандидатами на лучшего предшественника для некой позиции результата. Для результата в ячейке te[i] лучший предшественник, из которого можно сделать прыжок - это индекс максимума в окне размером y-x+1, отстоящим назад от текущей позиции на x
На каждом шаге проверяете, не устарел ли индекс в голове дека - если разница с текущим индексом превысила Y, удаляете голову.
Затем берете индекс, отстоящий от текущего на X, и сравниваете значение, соответствующее этому индексу, со значением, на которое указывает хвост дека. Пока te[i-X] больше или равен значению из хвоста - удаляете хвост - эти элементы больше не имеют шансов, т.к. есть моложе и дороже.
Добавляете te[i-X] в хвост.
Теперь голова содержит индекс лучшего предшественника для текущей позиции, и мы записываем в текущую позицию результата сумму kuv[i] + te[deque.head]
Каждый элемент добавляется и удаляется один раз, алгоритм линейный.
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main() {
vector<int> kuv = { 0, 12, 2, 13, 9, 4, 7, 15, 5, 12, 4, 7, 19, 2, 15, 7, 0 };
int n = kuv.size();
int x = 2;
int y = 5;
int imax;
vector<int> te(n);
deque <int> deq;
for (int i = x; i < n; i++) {
if (!deq.empty() && i - deq.front() >= y)
deq.pop_front();
while (!deq.empty() && te[i - x] >= te[deq.back()])
deq.pop_back();
deq.push_back(i - x);
te[i] = te[deq.front()] + kuv[i];
}
cout << te[n-1];
return 0;
}
Вывод от аналогичной Python программы (позиция, индексы в деке, результат)
[0, 12, 2, 13, 9, 4, 7, 15, 5, 12, 4, 7, 19, 2, 15, 7, 0]
2 [0] 2
3 [1] 13
4 [2] 11
5 [3] 17
6 [3, 4] 20
7 [5] 32
8 [6] 25
9 [7] 44
10 [7, 8] 36
11 [9] 51
12 [9, 10] 63
13 [11] 53
14 [12] 78
15 [12, 13] 70
16 [14] 78