Ответ 1
ПРИМЕЧАНИЕ. Я немного изменю ваше отношение к динамическому программированию, так что нет специального случая, если j = 0
. Теперь dp[j]
является ответом для первых j
терминов A[0], ..., A[j-1]
и:
dp[i] = min(dp[j] + max(A[j], ..., A[i-1]), i-k <= j < i)
Ответ проблемы теперь dp[n]
.
Обратите внимание, что если j < i
и dp[j] >= dp[i]
, вам не понадобится dp[j]
в следующих переходах, потому что max(A[j], ..., A[l]) >= max(A[i], ..., A[l])
(так что всегда лучше обрезать i
вместо j
.
Кроме того, пусть C[j] = max(A[j+1], ..., A[l])
(где l
- наш текущий индекс на этапе динамического программирования, т.е. i
в вашей программе на С++).
Затем вы можете сохранить в памяти некоторый набор индексов x1 < ... < xm
( "интересные" индексы для переходов вашего отношения к динамическому программированию), чтобы: dp[x1] < ... < dp[xm]
(1). Затем автоматически C[x1] >= ... >= C[xm]
(2).
Чтобы сохранить {x1, ..., xm}
, нам нужна некоторая структура данных, которая поддерживает следующие операции:
- Отбросить назад (когда мы переходим от
i
доi+1
, мы должны сказать, чтоi-k
теперь недоступен) или фронт (cf. insertion). - Нажимаем вперед
x
(когда мы вычислилиdp[i]
, вставим его, сохранив (1), удалив соответствующие элементы). - Вычислить
min(dp[xj] + C[xj], 1 <= j <= m)
.
Таким образом, будет достаточно одной очереди для хранения x1, ..., xk
вместе с set
для хранения всех dp[xi] + C[xi]
.
Как мы сохраняем (1) и обновляем C
при вставке элемента i
?
- Перед вычислением
dp[i]
мы обновимC
с помощьюA[i-1]
. Для этого найдем наименьший элементxj
в множествеx
s.t.C[xj] <= A[i-1]
. Тогда из (1) и (2) следует, чтоdp[j'] + C[j'] >= dp[j] + C[j]
для всехj' >= j
, поэтому мы обновляемC[xj]
доA[i-1]
и удаляемx(j+1), ..., xm
из набора (*). - Когда мы вставляем
dp[i]
, мы просто удаляем все элементы s.t.dp[j] >= dp[i]
, щелкнув спереди. - Когда мы удаляем
i-k
, возможно, что какой-то элемент, уничтоженный в (*), теперь становится лучше. Поэтому при необходимости мы обновляемC
и вставляем последний элемент.
Сложность: O(n log n)
(в наборе может быть не более 2n
вставки).
В этом коде суммируются основные идеи:
template<class T> void relaxmax(T& r, T v) { r = max(r, v); }
vector<int> dp(n + 1);
vector<int> C(n + 1, -INF);
vector<int> q(n + 1);
vector<int> ne(n + 1, -INF);
int qback = 0, qfront = 0;
auto cmp = [&](const int& x, const int& y) {
int vx = dp[x] + C[x], vy = dp[y] + C[y];
return vx != vy ? vx < vy : x < y;
};
set<int, decltype(cmp)> s(cmp);
dp[0] = 0;
s.insert(0);
q[qfront++] = 0;
for (int i = 1; i <= n; ++i) {
C[i] = A[i - 1];
auto it_last = lower_bound(q.begin() + qback, q.begin() + qfront, i, [=](const int& x, const int& y) {
return C[x] > C[y];
});
for (auto it = it_last; it != q.begin() + qfront; ++it) {
s.erase(*it);
C[*it] = A[i - 1];
ne[*it] = i;
if (it == it_last) s.insert(*it);
}
dp[i] = dp[*s.begin()] + C[*s.begin()];
while (qback < qfront && dp[q[qfront]] >= dp[i]) {
s.erase(q[qfront]);
qfront--;
}
q[qfront++] = i;
C[i] = -INF;
s.insert(i);
if (q[qback] == i - k) {
s.erase(i - k);
if (qback + 1 != qfront && ne[q[qback]] > q[qback + 1]) {
s.erase(q[qback + 1]);
relaxmax(C[q[qback + 1]], C[i - k]);
s.insert(q[qback + 1]);
}
qback++;
}
}
// answer: dp[n]
На этот раз я проверил его против вашего алгоритма: см. здесь.
Пожалуйста, дайте мне знать, если это все еще неясно.