bzoj1079 [ SCOI2008 ] --记忆化搜索
2018-06-17 23:25:31来源:未知 阅读 ()
题目大意:
有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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:C++整数转字符串的一种方法
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
- 洛谷P4133 [BJOI2012]最多的方案(记忆化搜索) 2018-09-18
- 记忆化搜索(例) 2018-07-17
- Josn转换 2018-06-18
- bzoj3208--记忆化搜索 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash