https://vjudge.net/problem/UVA-11982
题意：
给出一个包含’U’, ‘D’, ‘E’的字符串，
’U’ 表示需要把这个字符向后移动，
’D’表示需要把这个字符向前移动，
’E’表示这个字符不移动，
求移动方案
‘U’和‘D’都需要把这个字符拿起
dp[i][j] 表示前i个字符中，有j个‘U’还没放下的方案数
如果第i个是‘U’，那么这个‘U’必须拿走，
这个位置可以暂时空着，由dp[i-1][j-1]转移
这个位置可以从之前没有放下的‘U‘里选一个放下，由dp[i-1][j]*j 转移
如果第i个是‘D’，那么这个‘D’必须放到前面，
这个位置可以暂时空着，‘D’可以从前面的j个位置任选一个放下，由dp[i-1][j]*j 转移
这个位置可以从之前没有放下的j+1个‘U’里选一个放下，‘D’可以从前面的j+1个位置任选一个放下,由dp[i-1][j+1]*(j+1)*(j+1)转移
#include<cstdio> #include<cstring> #define mod 1000000007 using namespace std; long long dp[1001][1001]; char s[1001]; int len; int main() { int T; scanf("%d",&T); for(int t=1;t<=T;t++) { scanf("%s",s+1); len=strlen(s+1); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=len;i++) if(s[i]==‘U‘) for(int j=0;j<=i;j++) dp[i][j]=(dp[i][j]+dp[i-1][j-1]+dp[i-1][j]*j%mod)%mod; else if(s[i]==‘D‘) for(int j=0;j<=i;j++) dp[i][j]=(dp[i][j]+dp[i-1][j]*j%mod+dp[i-1][j+1]*(j+1)%mod*(j+1)%mod); else for(int j=0;j<=i;j++) dp[i][j]=dp[i-1][j]; printf("Case %d: %d\n",t,dp[len][0]); } }
原文：http://www.cnblogs.com/TheRoadToTheGold/p/7470699.html