概念

挿入型動的計画法（DP）とは、特定の順列に基づいてDPを行う問題で、計算量は一般的にO(n²)からO(n³)の範囲内です。この種の問題では、順列内の昇順や降順の変化点が答えに大きな影響を与えます。

基本的なアプローチは以下の通りです：

• 数値を小さい順に挿入し、その段階で状態設計を行います。これにより、既に挿入された数値は現在の数値より小さく、昇順や降順の制約を考慮する必要がありません。
• 状態は通常、dp[i][j]として定義され、これは1からiまでの数値が挿入され、j個の連続セグメントを形成する方法の数を表します。各セグメントは形成後は分割されませんが、セグメント間には新しい数値を挿入することができます。
• 最適化問題の場合、貢献度を事前に計算する手法が一般的です。

例題

Permutation

問題文

この問題では、数値の相対的な順位を使用して状態を設計します。dp[i][j]は、i個の数値が挿入され、最後の数値の相対的な順位がjである方法の数を表します。

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;
    }
}

[ABC209F] Deforestation

問題文

最小コストを達成するために、iとi+1のどちらかを先に取り除くべきかを決定します。この戦略に基づいて、dpテーブルを更新します。

for (int i = 1; i < n; ++i) {
    if (a[i] > a[i+1]) {
        dp[i+1][j] = (dp[i+1][j] + dp[i][j-1]) % mod;
    } else if (a[i] < a[i+1]) {
        dp[i+1][j] = (dp[i+1][j] + dp[i][j+1]) % mod;
    } else {
        dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod;
    }
}

[CEOI2016] kangaroo

問題文

この問題では、dp[i][j]を1からiまでの数値が挿入され、j個の連続セグメントを形成する方法の数として定義します。

if (i == s || i == t) {
    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
} else {
    if (i > s && i > t && i < n && j == 1) {
        // 特殊な処理
    } else {
        dp[i][j] = (dp[i][j] + (1LL * dp[i - 1][j + 1] * j) % mod) % mod;
        dp[i][j] = (dp[i][j] + (1LL * dp[i - 1][j - 1] * (j - (i > s) - (i > t))) % mod) % mod;
    }
}

Ant Man

問題文

最適化問題であり、貢献度を事前に計算します。状態設計は、最小コストを記録するように変更します。

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        dp[i][j] = min(dp[i][j], dp[i-1][j-1] + cost);
    }
}

[JOI Open 2016] 摩天大楼

問題文

この問題では、dp[i][j][k][l]を1からiまでの数値が挿入され、j個の連続セグメントを形成し、総コストがkでl個の端点が確定した方法の数として定義します。

int s = (a[i + 1] - a[i]) * (j * 2 - d) + k, Now = dp[i][j][k][d];
if (s > L || !Now) continue;
dp[i + 1][j + 1][s][d] = (dp[i + 1][j + 1][s][d] + (1LL * Now * (j + 1 - d)) % mod) % mod;
if (j >= 2) dp[i + 1][j - 1][s][d] = (dp[i + 1][j - 1][s][d] + (1LL * Now * (j - 1)) % mod) % mod;
if (j) dp[i + 1][j][s][d] = (dp[i + 1][j][s][d] + (1LL * Now * (j * 2 - d)) % mod) % mod;
if (d < 2) dp[i + 1][j + 1][s][d + 1] = (dp[i + 1][j + 1][s][d + 1] + (1LL * Now * (2 - d)) % mod) % mod;
if (d < 2 && j) dp[i + 1][j][s][d + 1] = (dp[i + 1][j][s][d + 1] + (1LL * Now * (2 - d)) % mod) % mod;

[ZJOI2012] 波浪

問題文

前の問題と同様ですが、最後にn!で割ります。K ≤ 8の場合、doubleを使用し、K ≤ 30の場合、__float128を使用します。

void Print(__float128 ans) {
    int num[maxn];
    num[0] = 0;
    ans = ans * 10;
    for (int i = 1; i < K; ++i) {
        num[i] = (int)ans;
        ans = (ans - num[i]) * 10;
    }
    num[K] = (int)(ans + 0.5);
    for (int i = K; i >= 1; --i) {
        if (num[i] >= 10) num[i] -= 10, num[i - 1]++;
    }
    printf("%d.", num[0]);
    for (int i = 1; i <= K; ++i) printf("%d", num[i]);
    puts("");
}

Phoenix and Computers

問題文

n ≤ 400の場合、直接dpテーブルを使用します。dp[i][j]は、i台のコンピュータが開かれ、そのうちj台が手動で開かれた方法の数を表します。

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        dp[i][j] = (dp[i-k-1][j-k] * g[k] * C[j][k]) % mod;
    }
}

[COCI2021-2022#2] Magneti

問題文

dp[i][j][k]は、i個の磁石がj組に分けられ、k個の空きスペースを占める方法の数を表します。

dp[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        for (int k = 1; k <= L; ++k) {
            int &p = dp[i][j][k];
            p = dp[i - 1][j - 1][k - 1];
            if (k > r[i]) p = (p + (2LL * dp[i - 1][j][k - r[i]] * j) % mod) % mod;
            if (k > 2 * r[i] - 1) p = (p + (1LL * (1LL * dp[i - 1][j + 1][k - (2 * r[i] - 1)] * (j + 1)) % mod * j) % mod) % mod;
        }
    }
}