HDOJ 5396 Expression：區間 DP 計算所有運算順序結果之和

問題重述

給定 n（≤ 100）個數字與 n−1 個運算符（+、−、*），按任意順序結合（每次選相鄰兩數及其間運算符計算），求所有可能運算順序的最終結果之和，模 10⁹+7。

DP 狀態定義

dp[l][r] = 區間 [l, r] 所有合法運算順序的結果總和。
cnt[l][r] = 該區間的合法運算順序數（卡特蘭數相關）。

轉移方程

枚舉最後一步在 k（l ≤ k < r）處結合：

• 運算符為 *：
   dp[l][r] += dp[l][k] × dp[k+1][r] × C(r−l−1, k−l)。
• 運算符為 + 或 −：
   左邊結果需乘以右邊方案數，右邊結果乘以左邊方案數。
   dp[l][r] += (dp[l][k] × cnt[k+1][r] ± dp[k+1][r] × cnt[l][k]) × C(r−l−1, k−l)。

其中 C 為組合數，表示左右子區間操作序列的交織方式數。

預計算

• 組合數 C[i][j] 遞推 O(n²)。
• 階乘 fact[i] 同步計算。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, MAXN = 105;
long long dp[MAXN][MAXN], cnt[MAXN][MAXN], C[MAXN][MAXN];
int a[MAXN]; char op[MAXN];
int main() {
    // 預計算組合數
    for (int i = 0; i < MAXN; ++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 n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        string s; cin >> s;
        for (int i = 1; i < n; ++i) op[i] = s[i-1];
        // 初始化長度 1
        for (int i = 1; i <= n; ++i) {
            dp[i][i] = a[i] % MOD;
            cnt[i][i] = 1;
        }
        // 區間 DP
        for (int len = 2; len <= n; ++len) {
            for (int l = 1; l + len - 1 <= n; ++l) {
                int r = l + len - 1;
                dp[l][r] = 0; cnt[l][r] = 0;
                for (int k = l; k < r; ++k) {
                    long long ways = C[r-l-1][k-l];
                    if (op[k] == '*') {
                        dp[l][r] = (dp[l][r] + dp[l][k] * dp[k+1][r] % MOD * ways) % MOD;
                    } else if (op[k] == '+') {
                        dp[l][r] = (dp[l][r] + (dp[l][k] * cnt[k+1][r] + dp[k+1][r] * cnt[l][k]) % MOD * ways) % MOD;
                    } else { // '-'
                        dp[l][r] = (dp[l][r] + (dp[l][k] * cnt[k+1][r] - dp[k+1][r] * cnt[l][k]) % MOD * ways) % MOD;
                    }
                    cnt[l][r] = (cnt[l][r] + cnt[l][k] * cnt[k+1][r] % MOD * ways) % MOD;
                }
            }
        }
        cout << (dp[1][n] % MOD + MOD) % MOD << '\n';
    }
    return 0;
}

複雜度

O(n³) 時間，n ≤ 100 約 10⁶ 狀態轉移，極快。