Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 2093  Solved: 1264

[][][]

Description

　　有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。

所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两

个相邻木块颜色不同的着色方案。

Input

　　第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。

Output

　　输出一个整数，即方案总数模1,000,000,007的结果。

Sample Input

3

1 2 3

Sample Output

10

HINT

 100%的数据满足：1 <= k <= 15, 1 <= ci <= 5

思路

因为油漆最多够涂五块，显然可以在这里动脑筋；

于是我们有了个六维DP，前五维分别代表能涂对应位置块的油漆种数，第六维代表上一次用的油漆那时够涂几块；

然后把油漆涂完，完事了；

注意，如果上一次用的还能涂i块的油漆，那么当前就有一种够涂i-1块的油漆无用，因为"相邻两个木块涂相同色显得很难看"；

代码实现

 

1 #include
      
        2 const int mod=1e9+7; 3 int k,a,s[6],dp[16][16][16][16][16][6]; 4 int dfs(int a1,int a2,int a3,int a4,int a5,int last){ 5     if(dp[a1][a2][a3][a4][a5][last]) return dp[a1][a2][a3][a4][a5][last]; 6     if(a1+a2+a3+a4+a5==0) return dp[a1][a2][a3][a4][a5][last]=1; 7     long long tot=0; 8     if(a1) tot+=1ll*(a1-(last==2))*dfs(a1-1,a2,a3,a4,a5,1),tot%=mod; 9     if(a2) tot+=1ll*(a2-(last==3))*dfs(a1+1,a2-1,a3,a4,a5,2),tot%=mod;10     if(a3) tot+=1ll*(a3-(last==4))*dfs(a1,a2+1,a3-1,a4,a5,3),tot%=mod;11     if(a4) tot+=1ll*(a4-(last==5))*dfs(a1,a2,a3+1,a4-1,a5,4),tot%=mod;12     if(a5) tot+=1ll*a5*dfs(a1,a2,a3,a4+1,a5-1,5),tot%=mod;13     return dp[a1][a2][a3][a4][a5][last]=tot;14 }15 int main(){16     scanf("%d",&k);17     for(int i=1;i<=k;i++){18         scanf("%d",&a);19         s[a]++;20     }21     printf("%d",dfs(s[1],s[2],s[3],s[4],s[5],0));22     return 0;23 }