[BZOJ 1079][SCOI 2008]着色方案
2024-10-12 20:23:14
1079: [SCOI2008]着色方案
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2237 Solved: 1361
[Submit][Status][Discuss]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 3Sample Output
10HINT
100%的数据满足:1 <= k <= 15, 1 <= ci <= 5
题解
令人恶心的一道 $DP$ ...
注意到 $k$ 的范围很小, 所以首先我们可以想到的定义状态的方案是把每种油漆剩余的数量定义进状态, 但是 $15$ 维的记忆化数组怕是是个人都不想写吧...而且$5^{15}\approx 3.05\times 10^{10}$ 并不能开得下...
但是我们会发现, 其实不同的油漆只要余量相等, 对于答案的影响并没有什么区别, 所以我们可以分别将余量为 $1,2,3,4,5$ 的油漆种数定义进状态, 再加一维表示上次用的是哪种油漆, $DFS$ 处理就好了
代码挺好写, 但看起来比较恶心...
参考代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm> const int MOD=1e9+;
const int MAXN=; int n;
int data[MAXN];
int dp[MAXN][MAXN][MAXN][MAXN][MAXN][]; int DFS(int,int,int,int,int,int); int main(){
scanf("%d",&n);
int tmp;
for(int i=;i<n;i++){
scanf("%d",&tmp);
data[tmp]++;
}
for(int i=;i<=;i++){
dp[][][][][][i]=;
}
printf("%d\n",DFS(data[],data[],data[],data[],data[],));
return ;
} int DFS(int r1,int r2,int r3,int r4,int r5,int last){
if(dp[r1][r2][r3][r4][r5][last]!=)
return dp[r1][r2][r3][r4][r5][last];
else{
long long tmp=;
if(r1>)
tmp+=1ll*(last==?r1-:r1)*DFS(r1-,r2,r3,r4,r5,);
if(r2>)
tmp+=1ll*(last==?r2-:r2)*DFS(r1+,r2-,r3,r4,r5,);
if(r3>)
tmp+=1ll*(last==?r3-:r3)*DFS(r1,r2+,r3-,r4,r5,);
if(r4>)
tmp+=1ll*(last==?r4-:r4)*DFS(r1,r2,r3+,r4-,r5,);
if(r5>)
tmp+=1ll*r5*DFS(r1,r2,r3,r4+,r5-,);
dp[r1][r2][r3][r4][r5][last]=tmp%MOD;
return dp[r1][r2][r3][r4][r5][last];
}
}
Backup
最新文章
- 读书笔记:《HTML5开发手册》--HTML5新的结构元素
- myeclipse学习总结二(myeclipse安装svn插件)
- jdbc java数据库连接 8)防止sql注入
- No.25
- Mac 效率工具
- Selenium2学习-039-WebUI自动化实战实例-文件上传下载
- mybatis3.2.3+spring3 控制台打印sql解决办法
- Ip地址查询
- linux中预留的$变量
- Java解析HTML之HTMLParser使用与详解
- 让谷歌浏览器 chrome 支持小于12px的字体
- STM32管教复用与重映射关系
- jQuery 实验教程
- [ionic开源项目教程] - 第5讲 如何在项目中使用全局配置
- 嵌入式 H264视频通过RTMP直播
- 在vs环境中跑动sift特征提取(原理部分)
- boost.asio源码阅读(1) - 从chat_server开始
- DOS命令(一)
- Filter过滤器 不登陆无法访问其他页面
- 从零开始学 Web 之 BOM(三)offset,scroll,变速动画函数