bzoj1079--记忆化搜索

2017-01-07 19:01:46来源:cnblogs.com作者:gjghfd人点击

第七城市

题目大意:
有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 }
bzoj1079

 

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台