DP дар зерқаторҳо

DP дар зерқаторҳо - Course 5

#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;
}

DP дар зерқаторҳо

Ин ки ин намуна чист

Шаблони стандартии DP

Ҳолат

База

Гузариш (маъмултарин)

Тартиби ҳисоб

Мисоли 1: Зерпайдарпаии палиндромии дарозтарин

Идея

Мураккабӣ

Мисоли 2: Бозии хориҷкунӣ (гирифтан аз канорҳо)

Идея

Мисоли 3: Арзиши ҳадди ақал барои якҷоякунӣ (Сангҳо / Слаймҳо)

Идея