HDU 5151 Sit sit sit 區間 DP 詳解：最大值放置與組合數應用

問題描述

給定長度為 N 的序列，每個位置有顏色值。需計算合法排列方案數：每次在區間中放置當前最大值，限制相鄰顏色不同的位置不能放最大值。結果模 10⁹+7。

動態規劃設計

定義 dp[i][j] 表示區間 [i, j] 的合法方案數。枚舉最大值放置位置 k (i ≤ k ≤ j)：

• 若 k = i：左側無元素，方案數為 dp[i+1][j]
• 若 k = j：右側無元素，方案數為 dp[i][j-1]
• 若 i < k < j 且 v[k-1] == v[k+1]：左右子區間獨立，需乘以組合數 C[len][left_len] 分配位置

狀態轉移方程

dp[l][r] += dp[l][k-1] * dp[k+1][r] % MOD * C[r-l][k-l] % MOD

預處理組合數

利用帕斯卡三角形預計算 C[n][k]，時間複雜度 O(N²)。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const long long MOD = 1e9+7;
int N, v[MAXN];
long long dp[MAXN][MAXN], C[MAXN][MAXN];

void init(int n) {
    for (int i = 0; i <= n; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
}

int solve() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; ++i) dp[i][i] = 1;
    for (int len = 1; len < N; ++len) {
        for (int l = 1; l + len <= N; ++l) {
            int r = l + len;
            for (int k = l; k <= r; ++k) {
                if (k == l) dp[l][r] = (dp[l][r] + dp[k+1][r]) % MOD;
                else if (k == r) dp[l][r] = (dp[l][r] + dp[l][k-1]) % MOD;
                else if (v[k-1] == v[k+1])
                    dp[l][r] = (dp[l][r] + dp[l][k-1] * dp[k+1][r] % MOD * C[r-l][k-l] % MOD) % MOD;
            }
        }
    }
    return dp[1][N];
}

int main() {
    init(100);
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; ++i) scanf("%d", &v[i]);
        printf("%d\n", solve());
    }
    return 0;
}

複雜度分析

• 時間：O(N³)，N ≤ 100 完全可行
• 空間：O(N²)

此題展示了區間 DP 結合組合數學的典型應用，關鍵在於正確處理最大值放置對左右子區間的分割與合併。