首页 > 代码库 > bzoj1079 [SCOI2008]着色方案

bzoj1079 [SCOI2008]着色方案

2024-08-05 15:59:04   215人阅读

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 3

Sample Output

10
 
这题没看题解做法真心想不出来啊……
首先，orz hzwer
f[a1][a2][a3][a4][a5][k]表示能刷1次的油漆还有a1种，刷2次的还有a2种，刷3次的还有a3种，刷4次的还有a4种，刷5次的还有a5种，上一个涂的是还能刷k次的某一种油漆的方案
前五维还是比较好理解的
转移也好想：对于还能刷k次的某一种油漆，如果当前使用了这一种，那么a[k]--,a[k-1]++。就是这种油漆只剩k-1次可以刷了
第六维是为了保证相邻两种油漆的种类不同。
如果上一次取的是还剩k次的一个颜色，那么这种颜色现在在a[k-1]中。所以计算现在取剩下k-1次的方案的时候要扣去这一个
然后就变成记忆化搜索
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define mod 1000000007using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}LL f[16][16][16][16][16][6];bool mrk[16][16][16][16][16][6];int rep[6];int n;inline LL cal(int a1,int a2,int a3,int a4,int a5,int from){	if (mrk[a1][a2][a3][a4][a5][from])return f[a1][a2][a3][a4][a5][from];	if (a1+a2+a3+a4+a5==0)return 1;	LL ans=0;	if (a1)ans+=(a1-(from==2))*cal(a1-1,a2,a3,a4,a5,1);	if (a2)ans+=(a2-(from==3))*cal(a1+1,a2-1,a3,a4,a5,2);	if (a3)ans+=(a3-(from==4))*cal(a1,a2+1,a3-1,a4,a5,3);	if (a4)ans+=(a4-(from==5))*cal(a1,a2,a3+1,a4-1,a5,4);	if (a5)ans+=a5*cal(a1,a2,a3,a4+1,a5-1,5);	ans%=mod;	mrk[a1][a2][a3][a4][a5][from]=1;	f[a1][a2][a3][a4][a5][from]=ans;	return f[a1][a2][a3][a4][a5][from];}int main(){	n=read();	for (int i=1;i<=n;i++)rep[read()]++;	printf("%lld\n",cal(rep[1],rep[2],rep[3],rep[4],rep[5],0));}

 

bzoj1079 [SCOI2008]着色方案


联系
我们