1079: [SCOI2008]著色方案

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?2826??Solved:?1682
[Submit][Status][Discuss]

Description

　　有n個(gè)木塊排成一行，從左到右依次編號(hào)為1~n。你有k種顏色的油漆，其中第i種顏色的油漆足夠涂ci個(gè)木塊。
所有油漆剛好足夠涂滿所有木塊，即c1+c2+...+ck=n。相鄰兩個(gè)木塊涂相同色顯得很難看，所以你希望統(tǒng)計(jì)任意兩
個(gè)相鄰木塊顏色不同的著色方案。

Input

　　第一行為一個(gè)正整數(shù)k，第二行包含k個(gè)整數(shù)c1, c2, ... , ck。

Output

　　輸出一個(gè)整數(shù)，即方案總數(shù)模1,000,000,007的結(jié)果。

Sample Input

3
1 2 3

Sample Output

10

HINT

?

?100%的數(shù)據(jù)滿足：1 <= k <= 15, 1 <= ci <= 5

一開(kāi)始想的組合數(shù)學(xué)，但顏色數(shù)太多沒(méi)法容斥。后來(lái)想到用dp，也想到用dp[a][b][c][d][e]維護(hù)數(shù)量為1，2,3,4,5,的顏色有a，b，c，d，e種的方案數(shù)，但是不太會(huì)遞推啊... 題解： 看黃學(xué)長(zhǎng)的題解用的記憶化搜索，用last記錄上一層用掉的是數(shù)量為last的顏色，那么該層能用的last-1的顏色就少了一個(gè)，用f[a][b][c][d][e][last]維護(hù)數(shù)量為1，2,3,4,5,的顏色有a，b，c，d，e種的方案數(shù)。 當(dāng)用掉一個(gè)數(shù)量為k的顏色時(shí)，增加的方案數(shù)為該層能用的數(shù)量為k的顏色數(shù)（即 num[k] -（last == k+1））*dfs(..,num[k-1]+1,num[k]-1,...,k)。 1 /************************************************************** 2 Problem: 1079 3 User: mizersy 4 Language: C++ 5 Result: Accepted 6 Time:88 ms 7 Memory:151292 kb 8 ****************************************************************/ 9 10 #include <bits/stdc++.h> 11 using namespace std; 12 typedef long long ll; 13 const ll mod = 1e9+7; 14 ll f[20][20][20][20][20][6]; 15 ll k,w; 16 ll num[10]; 17 18 ll dfs(ll a,ll b,ll c,ll d,ll e,ll last){ 19 if (f[a][b][c][d][e][last]) return f[a][b][c][d][e][last]; 20 ll ret = 0; 21 if (a) 22 ret = (ret + (a - (last == 2)) * dfs(a-1,b,c,d,e,1) % mod) % mod; 23 if (b) 24 ret = (ret + (b - (last == 3)) * dfs(a+1,b-1,c,d,e,2) % mod) % mod; 25 if (c) 26 ret = (ret + (c - (last == 4)) * dfs(a,b+1,c-1,d,e,3) % mod) % mod; 27 if (d) 28 ret = (ret + (d - (last == 5)) * dfs(a,b,c+1,d-1,e,4) % mod) % mod; 29 if (e) 30 ret = (ret + e * dfs(a,b,c,d+1,e-1,5) % mod) % mod; 31 return f[a][b][c][d][e][last] = ret % mod; 32 } 33 34 35 int main(){ 36 scanf("%lld",&k); 37 for (int i = 1;i <= k;++i){ 38 scanf("%lld",&w); 39 num[w]++; 40 } 41 for (int i = 0;i <= 5;++i) f[0][0][0][0][0][i] = 1; 42 printf("%lld\n",dfs(num[1],num[2],num[3],num[4],num[5],0)); 43 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/mizersy/p/9565955.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1079 [SCOI2008]着色方案 记忆化搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。