2015 Multi-University Training Contest 9
设d[i][j] 代表i~j的答案。区间DP枚举(i, j)区间的断点，如果断点处的操作符是‘*’，那么该区间的答案可以直接加上d[i][k] * d[k+1][j]，因为乘法分配律可以保证所有的答案都会乘起来。如果是加法，需要加的 就是 左边的答案 乘 右边操作数的阶乘 加上 右边的答案乘左边操作数的阶乘，最后要确定左边操作和右边操作的顺序 因为每个答案里是统计了该区间所有的阶乘情况，因此每一个左边已确定的顺序和右边已确定的顺序需要排列组合一下。比如：左边有3个操作数+-*，右边有2个操作符+-，当已经确定了他们各自的顺序，假设左边算-*+，右边+-，这个顺序已经固定，现在有五个操作符需要操作，我需要选择三个位置给左边的操作符-*+，那么右边的两个操作符自然就对应他们相应的位置。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define N 106 6 #define MOD 1000000007 7 #define ll long long 8 ll A[N]={1}; 9 ll C[N][N]={1}; 10 ll dp[N][N]; 11 char op[N]; 12 void init() 13 { 14 A[0]=1; 15 for(ll i=1;i<N;i++) 16 A[i]=A[i-1]*i%MOD; 17 18 for(ll i=1;i<N;i++) 19 C[i][i]=C[i][0]=1; 20 for(int i=1;i<N;i++) 21 { 22 for(ll j=1;j<i;j++) 23 C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; 24 } 25 } 26 int main() 27 { 28 init(); 29 ll n; 30 while(scanf("%I64d",&n)==1) 31 { 32 memset(dp,0,sizeof(dp)); 33 for(ll i=0;i<n;i++) 34 { 35 scanf("%I64d",&dp[i][i]); 36 } 37 scanf("%s",op); 38 39 for(ll len=1;len<=n;len++) 40 { 41 for(ll i=0;i+len<n;i++) 42 { 43 ll j=i+len; 44 for(ll k=i;k<j;k++) 45 { 46 ll tmp; 47 if(op[k]==‘+‘) 48 { 49 tmp=(dp[i][k]*A[j-k-1]+dp[k+1][j]*A[k-i])%MOD; 50 } 51 else if(op[k]==‘-‘) 52 { 53 tmp=(dp[i][k]*A[j-k-1]-dp[k+1][j]*A[k-i])%MOD; 54 tmp=(tmp+MOD)%MOD; 55 } 56 else 57 { 58 tmp=(dp[i][k]*dp[k+1][j])%MOD; 59 } 60 tmp=tmp*C[j-i-1][k-i]%MOD; 61 dp[i][j]=(dp[i][j]+tmp+MOD)%MOD; 62 } 63 } 64 } 65 printf("%I64d\n",dp[0][n-1]); 66 } 67 return 0; 68 }
原文：http://www.cnblogs.com/UniqueColor/p/4741033.html
