hdu 5396 Expression（區間dp+組合數）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5396

解題思路：

題目大意：

題目大意：有n個數，和n-1個符号（'+','-','*'）形成一個表達式，現在問對于不同的運算序列，得到的結果的總和是多少（結果為非負整數，對1e9+7取餘）

dp[i][j]記錄在區間l到r内的各種不同的運算序列的結果的和。

官方題解：

記dp_{l,r}dp​l,r​​表示l,rl,r這段數能形成的答案總和。

枚舉最後一步操作kk，如果是乘法，答案為dp_{l,k}*dp_{k+1,r}dp​l,k​​∗dp​k+1,r​​，由于配置設定率這個會乘開來。如果是加法那麼是dp_{l,r}*(r-k-1)!+dp_{k+1,r}*(k-l)!dp​l,r​​∗(r−k−1)!+dp​k+1,r​​∗(k−l)!，即要乘上右邊k+1,rk+1,r這些數所有可行的方案數，減法同理。最後乘上{r-l-2 \choose k-l}(​k−l​r−l−2​​)，即把兩邊操作合起來的方案數。

答案為dp_{1,n}dp​1,n​​。

算法思想：

首先長度len是1的時候，dp[i][i] = a[i]

之後dp[i][j] = ∑ (dp[i][k] 和 dp[k+1][j] 合并而成),k為[i,j]範圍内的運算符号，那麼分三種情況:

1、'+'

對于dp[i][k]共有k-l個符号，也就是有(k-i)!種不同的運算序列，dp[k+1][j]有(j-k-1)!種運算序列，那麼對于不同的運算序列得到的值應該累加，是以累加的和為dp[i][k]*(j-k-1)! + dp[k+1][j]*(k-i)，同時還要注意，這種運算序列是符号j的左右兩側分開考慮的，如果交叉考慮，隻要各自相對的運算順序沒變，那麼值就不會變，但會形成新的一種運算方法，是以最終的值還要再乘以C(j-i-1 , k-i)。

2、'-'

和加法基本相同，隻需要把加換成減。

3、'*'

對于乘法，我們需要的結果是左右表達式中的各種運算方式得到的值分别相乘然後累加和，這個結果就可以直接轉化為dp[i][k]*dp[k+1][j]，同樣我們還需要對最終的結果乘以C(j-i-1 , k-i)

注意取餘，最終的dp[0][n-1]就是結果

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const int MOD = 1e9+7;
const int maxn = 100;
ll c[maxn+5][maxn+5],f[maxn+5];
ll dp[maxn+5][maxn+5];
char op[maxn+5];

void init(){
    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]+c[i-1][j-1])%MOD;
    }
    f[0] = 1;
    for(int i = 1; i <= maxn; i++)
        f[i] = f[i-1]*i%MOD;
}

int main () {
    init ();
    int n;
    while (~scanf("%d",&n)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
            scanf("%d", &dp[i][i]);
        getchar();
        gets(op);
        for (int i = n-1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                int len = j - i - 1;
                for (int k = i; k < j; k++) {
                    int l = k - i, r = j - k - 1;

                    ll ret = 0;
                    if (op[k] == '+') {
                        ret = (ret + dp[i][k] * f[r]) % MOD;
                        ret = (ret + dp[k+1][j] * f[l]) % MOD;

                    }
                    else if (op[k] == '-') {
                        ret = (ret + dp[i][k] * f[r]) % MOD;
                        ret = ((ret - dp[k+1][j] * f[l]) % MOD + MOD) % MOD;
                    }
                    else if (op[k] == '*')
                        ret = dp[i][k] * dp[k+1][j] % MOD;
                    dp[i][j] = (dp[i][j] + ret * c[len][l]) % MOD;
                }
                //printf("%d %d: %d\n", i, j, dp[i][j]);
            }
        }
        printf("%lld\n", dp[0][n-1]);
    }
    return 0;
}