bzoj1079--記憶化搜索，bzoj1079--記憶搜索

bzoj1079--記憶化搜索，bzoj1079--記憶搜索

題目大意：
有n個木塊排成一行，從左到右依次編號為1~n。你有k種顏色的油漆，其中第i種顏色的油漆足夠塗ci個木塊。
所有油漆剛好足夠塗滿所有木塊，即c1+c2+...+ck=n。相鄰兩個木塊塗相同色顯得很難看，所以你希望統計任意兩
個相鄰木塊顏色不同的著色方案。

題解：
看到數據范圍第一個想到的就是dp。但5^15顯然不現實。注意到ci相等的顏色本質上是相同的，於是可以記憶化搜索。

時間復雜度：O(15^5)

代碼：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define mod 1000000007
 6 #define ll long long
 7 int i,j,k,n,m,s[6];
 8 ll f[16][16][16][16][16][6];
 9 inline ll Dfs(int a,int b,int c,int d,int e,int l){
10     ll Sum=0;
11     if(f[a][b][c][d][e][l])return f[a][b][c][d][e][l];
12     if(a+b+c+d+e==0)return 1;
13     if(a)Sum+=(a-(l==2))*Dfs(a-1,b,c,d,e,1);
14     if(b)Sum+=(b-(l==3))*Dfs(a+1,b-1,c,d,e,2);
15     if(c)Sum+=(c-(l==4))*Dfs(a,b+1,c-1,d,e,3);
16     if(d)Sum+=(d-(l==5))*Dfs(a,b,c+1,d-1,e,4);
17     if(e)Sum+=e*Dfs(a,b,c,d+1,e-1,5);
18     return f[a][b][c][d][e][l]=Sum%mod;
19 }
20 int main()
21 {
22     scanf("%d",&n);
23     for(i=1;i<=n;i++){
24         scanf("%d",&k);
25         s[k]++;
26     }
27     printf("%lld",Dfs(s[1],s[2],s[3],s[4],s[5],0));
28     return 0;
29 }