TC SRM 551 div2 题解
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
终于在TC过了两题，可惜第三题看错了题目。
250pt：只需要判断有几种颜色即可。
int dp[3][3][51][51][51];int cnt[3],n;class ColorfulCupcakesDivTwo{public:int slove(int pos,int pre,int fst,int a,int b,int c){if(a<0||b<0||c<0)return 0;if(pos==n)return pre!=fst;if(dp[fst][pre][a][b][c]!=-1)return dp[fst][pre][a][b][c];int ret=0;if(pos==0){ret=(ret+slove(pos+1,0,0,a-1,b,c))%MOD;ret=(ret+slove(pos+1,1,1,a,b-1,c))%MOD;ret=(ret+slove(pos+1,2,2,a,b,c-1))%MOD;}else if(pre==0){ret=(ret+slove(pos+1,fst,1,a,b-1,c))%MOD;ret=(ret+slove(pos+1,fst,2,a,b,c-1))%MOD;}else if(pre==1){ret=(ret+slove(pos+1,fst,0,a-1,b,c))%MOD;ret=(ret+slove(pos+1,fst,2,a,b,c-1))%MOD;}else if(pre==2){ret=(ret+slove(pos+1,fst,0,a-1,b,c))%MOD;ret=(ret+slove(pos+1,fst,1,a,b-1,c))%MOD;}return dp[fst][pre][a][b][c]=ret;}int countArrangements(string cupcakes){cnt[0]=cnt[1]=cnt[2]=0;n=cupcakes.size();for(int i=0;i<n;i++)cnt[cupcakes[i]-'A']++;memset(dp,-1,sizeof(dp));return slove(0,0,0,cnt[0],cnt[1],cnt[2]);}};/*int dp[51][51][51][51][3];int countArrangements(string cupcakes){cnt[0]=cnt[1]=cnt[2]=0;int n=cupcakes.size();for(int i=0;i<n;i++)cnt[cupcakes[i]-'A']++;int ans=0;for(int s=0;s<3;s++){memset(dp,0,sizeof(dp));if(s==0)dp[1][1][0][0][0]=1;else if(s==1)dp[1][0][1][0][1]=1;elsedp[1][0][0][1][2]=1;for(int x=2;x<=n;x++){for(int a=0;a<=cnt[0];a++)for(int b=0;b<=cnt[1];b++)for(int c=0;c<=cnt[2];c++)if(a+b+c==x){if(a){dp[x][a][b][c][0]=(dp[x][a][b][c][0]+dp[x-1][a-1][b][c][1])%MOD;dp[x][a][b][c][0]=(dp[x][a][b][c][0]+dp[x-1][a-1][b][c][2])%MOD;}if(b){dp[x][a][b][c][1]=(dp[x][a][b][c][1]+dp[x-1][a][b-1][c][0])%MOD;dp[x][a][b][c][1]=(dp[x][a][b][c][1]+dp[x-1][a][b-1][c][2])%MOD;}if(c){dp[x][a][b][c][2]=(dp[x][a][b][c][2]+dp[x-1][a][b][c-1][1])%MOD;dp[x][a][b][c][2]=(dp[x][a][b][c][2]+dp[x-1][a][b][c-1][0])%MOD;}}}ans+=(((-dp[n][cnt[0]][cnt[1]][cnt[2]][s]+dp[n][cnt[0]][cnt[1]][cnt[2]][0]+dp[n][cnt[0]][cnt[1]][cnt[2]][2]))+dp[n][cnt[0]][cnt[1]][cnt[2]][1])%MOD; cout<<ans<<endl;}return ans;}*/