Qism massivlar bo‘yicha DP
Qism-massivlar bo‘yicha DP (shuningdek interval DP / diapazonlar bo‘yicha DP deb ham ataladi) kesma uchun javobni uning ichidagi kichikroq kesmalar javoblaridan hisoblash mumkin bo‘lganda ishlatiladi. Juda tipik holat:
Bu siz kesmani ikki kichik qismga bo‘lib «qurayotganingizda», yoki qisqaroq intervallardan uzunroqlariga kengayib borayotganingizda uchraydi.
uchun ni aniqlang.
Odatda:
Intervalni nuqtada bo‘lish:
Bu yerda masalaga bog‘liq (yig‘indi, max, min va h.k.).
Uzunlik ortib borish tartibida hisoblang:
Masala: satri berilgan, palindrom bo‘ladigan eng uzun qism-ketma-ketlik uzunligini toping.
= qism-satridagi LPS uzunligi bo‘lsin.
Vaqt bo‘yicha , xotira bo‘yicha ( gacha optimallashtirish mumkin, lekin oddiy qoldiramiz).
Masala: massivi. Ikki o‘yinchi navbatma-navbat yoki eng chap, yoki eng o‘ng elementni oladi. Ikkalasi ham optimal o‘ynaydi. Birinchi o‘yinchi to‘plashi mumkin bo‘lgan maksimal ochkoni toping.
Ochko farqi bilan ishlash:
Shunda:
Masala: massivi berilgan. Faqat qo‘shni segmentlarni birlashtirish mumkin. va ni birlashtirish narxi . Hammasini bitta uyumga birlashtirish uchun minimal umumiy narxni toping.
= qism-massivini bitta uyumga birlashtirishning minimal narxi bo‘lsin.
Baza:
O‘tish:
ni da hisoblash uchun prefiks yig‘indilaridan foydalaning.
Yakuniy murakkablik b bo‘ladi.
#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;
}