SCOI2008 着色方案

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2008 着色方案

Date: Fri Sep 07 09:52:27 CST 2018

In Category: NoCategory

Description：

有 $n$ 个木块 $k$ 种油漆，第 $i$ 种油漆够涂 $c_i$ 个木块。求任意两个相邻木块颜色不同的着色方案。

$1\le k \le 15,1\le c_i\le 5$

Solution：

发现剩余油漆如果能涂的个数相同那么他们对答案的贡献相同，于是 $f[cnt1][cnt2][cnt3][cnt4][cnt5][last]$ 记搜。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int k;

#define MAXK 16

#define MAXN 6

int t[MAXK];

#define MOD 1000000007

typedef long long ll;

ll f[MAXK][MAXK][MAXK][MAXK][MAXK][6];

ll dp(int a,int b,int c,int d,int e,int last)

{

	if(f[a][b][c][d][e][last] != -1)return f[a][b][c][d][e][last];

	if(a == 0 && b == 0 && c == 0 && d == 0 && e == 0)return (f[a][b][c][d][e][last] = 1);

	ll res = 0;

	if(a > 0)res += (a - (last == 2)) * dp(a - 1,b,c,d,e,1);

	if(b > 0)res += (b - (last == 3)) * dp(a + 1,b - 1,c,d,e,2);

	if(c > 0)res += (c - (last == 4)) * dp(a,b + 1,c - 1,d,e,3);

	if(d > 0)res += (d - (last == 5)) * dp(a,b,c + 1,d - 1,e,4);

	if(e > 0)res += e * dp(a,b,c,d + 1,e - 1,5);

	return (f[a][b][c][d][e][last] = (res % MOD));

}

int main()

{

	memset(f,-1,sizeof(f));

	scanf("%d",&k);

	int x;

	for(int i = 1;i <= k;++i)

	{

		scanf("%d",&x);

		++t[x];

	}

	printf("%lld\n",dp(t[1],t[2],t[3],t[4],t[5],0));

	return 0;

}

In tag: DP-记忆化搜索

wjh15101051