记dp_{l,r}dp?l,r??表示$l,r$这段数能形成的答案总和。

枚举最后一步操作$k$，如果是乘法，答案为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,r$这些数所有可行的方案数，减法同理。最后乘上{r-l-2 \choose k-l}(?k?l?r?l?2??)，即把两边操作合起来的方案数。

答案为dp_{1,n}dp?1,n??。

Expression

3
3 2 1
-+
5
1 4 6 8 3
+*-*

2
999999689
Hint
 Two numbers are considered different when they are in different positions.
 

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月19日 星期三 21时58分12秒
File Name     :HDOJ5396.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long int LL;

const int maxn=210;
const LL mod=1e9+7LL;

int n;
LL a[maxn];
char ope[maxn],cmd[maxn];
LL dp[maxn][maxn];
LL C[maxn][maxn];
LL jc[maxn];

void init()
{
	jc[0]=1; C[0][0]=1LL;
	for(int i=1;i<maxn;i++) 
	{
		C[i][i]=C[i][0]=1LL;
		jc[i]=(jc[i-1]*i)%mod;
	}
	for(int i=1;i<maxn;i++)
	{
		for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
}

void DP()
{
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i]=a[i];
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)
			{
				int left=k-i;
				int right=len-2-left;
				LL t=0;
				if(ope[k]=='*')
				{
					t=(dp[i][k]*dp[k+1][j])%mod;
				}
				else if(ope[k]=='+')
				{
					t=(dp[i][k]*jc[right]%mod+dp[k+1][j]*jc[left]%mod)%mod;
				}
				else if(ope[k]=='-')
				{
					t=(dp[i][k]*jc[right]%mod-dp[k+1][j]*jc[left]%mod+mod)%mod;
				}
				dp[i][j]=(dp[i][j]+t*C[len-2][left]%mod)%mod;
			}
		}
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	init();
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%lld",a+i);
		scanf("%s",cmd+1);
		for(int i=1;i<n;i++) ope[i]=cmd[i];
		DP();
		printf("%lld\n",dp[1][n]%mod);
	}
    
    return 0;
}

HDOJ 5396 Expression DP

原文：http://blog.csdn.net/ck_boss/article/details/47792355