BZOJ1079 [SCOI2008]着色方案 【dp记忆化搜索】
2024-08-29 12:55:37
题目
有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂ci个木块。
所有油漆刚好足够涂满所有木块,即c1+c2+…+ck=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两
个相邻木块颜色不同的着色方案。
输入格式
第一行为一个正整数k,第二行包含k个整数c1, c2, … , ck。
输出格式
输出一个整数,即方案总数模1,000,000,007的结果。
输入样例
3
1 2 3
输出样例
10
提示
100%的数据满足:1 <= k <= 15, 1 <= ci <= 5
题解
乍一看还以为是普通的dp,发现颜色次数限制还真不好整。
但不同颜色是没有什么区别的【只在与上一个颜色冲不冲突的问题上有区别】
观察颜色使用次数很少,我们尝试不用颜色作为状态,用所剩次数作为状态
设f[a][b][c][d][e][k]表示可用1次的颜色有a个,可用2次的颜色有b个,可用3次的颜色有c个,可用4次的颜色有d个,可用5次的颜色有e个,上一次使用的颜色为当前还剩k个的颜色
那么状态转移时我们就可以枚举这次涂上哪一个
比如涂上可用3次的颜色,那么就有c∗f[a][b+1][c−1][d][e]种方案,如果k==c,那么只有(c−1)∗f[a][b+1][c−1][d][e]种,因为c种颜色中有一种上一次涂上了
其它也是类似的。
用记忆化搜索会好写一些
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
using namespace std;
const int maxn = 105,maxm = 16,INF = 1000000000,P = 1000000007;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int N = 0,K,s[maxn];
LL f[maxm][maxm][maxm][maxm][maxm][6];
bool vis[maxm][maxm][maxm][maxm][maxm][6];
LL dp(int a,int b,int c,int d,int e,int k){
LL t = 0;
if (vis[a][b][c][d][e][k]) return f[a][b][c][d][e][k];
if (a + b + c + d + e == 0) return 1;
if (a) t = (t + (LL)(a - (k == 2)) * dp(a - 1,b,c,d,e,1)) % P;
if (b) t = (t + (LL)(b - (k == 3)) * dp(a + 1,b - 1,c,d,e,2)) % P;
if (c) t = (t + (LL)(c - (k == 4)) * dp(a,b + 1,c - 1,d,e,3)) % P;
if (d) t = (t + (LL)(d - (k == 5)) * dp(a,b,c + 1,d - 1,e,4)) % P;
if (e) t = (t + (LL)e * dp(a,b,c,d + 1,e - 1,5)) % P;
vis[a][b][c][d][e][k] = true;
return f[a][b][c][d][e][k] = t;
}
int main(){
K = RD();
REP(i,K) s[RD()]++;
printf("%lld\n",dp(s[1],s[2],s[3],s[4],s[5],0));
return 0;
}
最新文章
- Delphi JCL JEDI使用 jclDebug
- [JavaWeb 用MyEclipse分别创建最简单的JSP程序和Servlet程序]
- Java SAX Schema Validation
- atoi、stoi、strtoi区别
- bootstrap的流式布局
- 一 VC2008环境中ICE的配置
- WPF之路五:wpf 隐藏与显示 Visibility
- 转载 Unity Text 插入超链接
- winSockets编程(二)socket函数
- TTPRequest 提示#import <;libxml/HTMLparser.h>;找不到 的解决方法
- Spring里的aop实现方式和源码分析
- ipconfig会出现多个IP地址
- zoj 1760 查找
- input获取焦点软键盘弹出影响定位
- javaweb之请求的转发和重定向
- Python学习系列----第五章 模块
- 网络知识===TCP/UDP的区别
- Java for LeetCode 083 Remove Duplicates from Sorted List
- python之自定义排序函数sorted()
- 线程安全-一个VC下多个网络请求
热门文章
- C#后台动态添加Grid表格
- 洛谷P1437 [HNOI2004]敲砖块(dp)
- 最小化 Java 镜像的常用技巧
- day2_作业1(购物车)
- 477. Total Hamming Distance
- iOS-xib的使用1
- caioj:1682: 【贪心】买一送一
- lan口和wan口的配置
- 宁夏邀请赛F FLOYD
- Error: Cannot find module &#39;core-js/fn/array/values&#39; at Function.Module._resolveFilename (module