ДП по подмассивам
DP по подмассивам (также называется интервальный DP / DP по диапазонам) используется, когда ответ для отрезка можно вычислить из ответов для меньших отрезков внутри него. Очень типичное состояние:
Это встречается, когда вы «строите» отрезок, разбивая его на две меньшие части, или когда вы расширяетесь от более коротких интервалов к более длинным.
Определите для .
Обычно:
Разбить интервал в точке :
Где зависит от задачи (сумма, max, min и т. д.).
Считать по возрастанию длины:
Задача: Дана строка , найдите длину наибольшей подпоследовательности, которая является палиндромом.
Пусть = длина LPS в подстроке .
по времени, по памяти (можно оптимизировать до , но оставим просто).
Задача: Массив . Два игрока по очереди берут либо самый левый, либо самый правый элемент. Оба играют оптимально. Найдите максимальный счёт, который может набрать первый игрок.
Работать с разностью очков:
Тогда:
Задача: Дан массив . Можно сливать только соседние сегменты. Слияние и стоит . Найдите минимальную суммарную стоимость, чтобы слить всё в одну кучу.
Пусть = минимальная стоимость слить подмассив в одну кучу.
База:
Переход:
Используйте префиксные суммы, чтобы вычислять за .
Итоговая сложность будет b .
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = (int)s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == s[r]) {
dp[l][r] = 2 + (l + 1 <= r - 1 ? dp[l + 1][r - 1] : 0);
} else {
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
}
}
}
cout << dp[0][n - 1] << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
long long sum = 0;
for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = a[i];
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
}
}
long long diff = dp[0][n - 1];
long long first = (sum + diff) / 2;
cout << first << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1), pref(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
auto sum = [&](int l, int r) -> long long {
return pref[r] - pref[l - 1];
};
const long long INF = (1LL << 60);
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, INF));
for (int i = 1; i <= n; i++) dp[i][i] = 0;
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
long long add = sum(l, r);
for (int k = l; k < r; k++) {
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + add);
}
}
}
cout << dp[1][n] << "\n";
return 0;
}