950 PT:
题意：
给三种颜色的蛋糕A、B、C，每种有a,b,c个，共n个。
要把n个蛋糕放成一圈，相邻的两个颜色不能相同。
思路：
DP：记忆化搜索！ dp[n][s[0]][s[1]][d][l]表示：还需要放n个，第一种还有s[0]个，第二种还有s[1]个，当前放的是第d种，最后一个是l种的方案数。
f(n,s,d,l)求还有n个需要放，当前放的是第d种，最后一个放的是第l种。s是个数数组。
#define mod 1000000007
#define maxn 52
using namespace std;
long long dp[maxn][maxn][maxn][3][3];
class ColorfulCupcakesDivTwo{
public:
long long f(int n,int s[],int d,int l){
if (n==0 && d!=l)
return 1;
if (n==0)
return 0;
if (dp[n][s[0]][s[1]][d][l]!=-1)
dp[n][s[0]][s[1]][d][l];
long long ans=0;
for (int i=0;i<3;i++)
if (i!=d && s[i])
{
s[i]--;
ans+=f(n-1,s,i,l);
ans %=mod;
s[i]++;
}
return dp[n][s[0]][s[1]][d][l]=ans;
}
int countArrangements(string cupcakes){
memset(dp,-1,sizeof(dp));
int s[3]={0,0,0};
int N=cupcakes.length();
for (int i=0;i<N;i++)
s[cupcakes[i]-'A']++;
long long ans=0;
for (int i=0;i<3;i++)
if (s[i])
{
s[i]--;
ans+=f(N-1,s,i,i);
ans %=mod;
s[i]++;
}
return ans;
}
};