1079: [SCOI2008]著色方案

Time Limit:?10 Sec??Memory Limit:?162 MB

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

?

Source

?

所以用F[a][b][c][d][e][l]表示當前有能涂1次的油漆a個，能涂2次的b個….前一個顏色為l，再搞下轉移就行了。

?

1 #include<iostream> 2 #include<cstdio> 3 #define ll long long 4 #define mod 1000000007 5 using namespace std; 6 ll f[16][16][16][16][16][6];int x[6],n; 7 bool mark[16][16][16][16][16][6]; 8 ll dp(int a,int b,int c,int d,int e,int k) 9 { 10 ll t=0; 11 if(mark[a][b][c][d][e][k])return f[a][b][c][d][e][k]; 12 if(a+b+c+d+e==0)return 1; 13 if(a) 14 t+=(a-(k==2))*dp(a-1,b,c,d,e,1); 15 if(b) 16 t+=(b-(k==3))*dp(a+1,b-1,c,d,e,2); 17 if(c) 18 t+=(c-(k==4))*dp(a,b+1,c-1,d,e,3); 19 if(d) 20 t+=(d-(k==5))*dp(a,b,c+1,d-1,e,4); 21 if(e) 22 t+=e*dp(a,b,c,d+1,e-1,5); 23 mark[a][b][c][d][e][k]=1; 24 return f[a][b][c][d][e][k]=(t%mod); 25 } 26 int main() 27 { 28 scanf("%d",&n); 29 for(int i=1;i<=n;i++) 30 { 31 int t; 32 scanf("%d",&t); 33 x[t]++; 34 } 35 printf("%lld",dp(x[1],x[2],x[3],x[4],x[5],0)); 36 return 0; 37 }

?

轉載于:https://www.cnblogs.com/WQHui/p/8575529.html

總結

以上是生活随笔為你收集整理的bzoj1079: [SCOI2008]着色方案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。