[ SCOI 2008 ] 着色方案

\(\\\)

\(Description\)

给出\(K\)种颜料各自的个数\(C_i\)，每一个颜料只够涂一个格子，求将颜料用完，涂一排格子，每个格子只能涂一次的条件下，相邻两个格子的颜色互不相同的方案数对\(10^9+7\)取模的结果。

\(K\in [1,15]\)，\(C_i\in [1,5]\)

\(\\\)

\(Solution\)

想的map压缩状态量记搜挂了

想的容斥记搜求组合数排列数取反挂了

正解真是神仙计数题做的还是少，基本的思路模型还是没有。

注意到颜色相同的颜料性质是一致的。
基于开始想的两种方案状态量太大，记搜也会超时，而将一类颜料看作一种之后，状态量大大减少，相当于只有\(5\)种颜料，状态里还需记录上一个颜料属于哪一类即可。
设计状态\(f[n_1][n_2][n_3][n_4][n_5][last]\)表示，剩余个数分别为\(1\text~5\)的颜料各有几个，上一次使用的颜料使用前剩几个，此时到用完所有颜料的总涂色方案数。
搜起来就很简单啦，直接考虑搜哪一位递归下去，到全是\(0\)了答案就是\(1\)，搜完累计答案时，因为一类颜料是相同的，所以直接乘上该决策的可行颜料个数。
一些就我会犯的zz错误细节要注意：
- 优先判断搜索的颜料还有没有再考虑搜没搜到过，否则会数组越界
- 注意到状态设计是使用前剩几个所以判断可行颜料个数时，判断时应该是上一个是否是当前\(+1\)而不是是否相同，因为你拿了一次个数一定减了一个\(1\)。
- \(+1-1\)的时候注意是成对存在的不要光顾着-1
这样搜索的优越性在于，他的状态量少，代表性强，只关心相同性质的数的个数，与一些问题的精简状态量思想异曲同工但就是想不到在这里用。

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define R register

#define gc getchar

#define mod 1000000007ll

using namespace std;

typedef long long ll;

inline ll rd(){

  ll x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

ll n,s[10],f[16][16][16][16][16][10];

void dfs(ll n1,ll n2,ll n3,ll n4,ll n5,ll lst){

  if((n1|n2|n3|n4|n5)==0ll){f[0][0][0][0][0][lst]=1ll;return;}

  if(n1>0ll&&!f[n1-1][n2][n3][n4][n5][1]) dfs(n1-1,n2,n3,n4,n5,1);

  if(n2>0ll&&!f[n1+1][n2-1][n3][n4][n5][2]) dfs(n1+1,n2-1,n3,n4,n5,2);

  if(n3>0ll&&!f[n1][n2+1][n3-1][n4][n5][3]) dfs(n1,n2+1,n3-1,n4,n5,3);

  if(n4>0ll&&!f[n1][n2][n3+1][n4-1][n5][4]) dfs(n1,n2,n3+1,n4-1,n5,4);

  if(n5>0ll&&!f[n1][n2][n3][n4+1][n5-1][5]) dfs(n1,n2,n3,n4+1,n5-1,5);

  if(n2>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n2-(lst==3))*f[n1+1][n2-1][n3][n4][n5][2])%=mod;

  if(n3>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n3-(lst==4))*f[n1][n2+1][n3-1][n4][n5][3])%=mod;

  if(n4>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n4-(lst==5))*f[n1][n2][n3+1][n4-1][n5][4])%=mod;

  if(n1>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n1-(lst==2))*f[n1-1][n2][n3][n4][n5][1])%=mod;

  if(n5>0ll)(f[n1][n2][n3][n4][n5][lst]+=n5*f[n1][n2][n3][n4+1][n5-1][5])%=mod;

}

int main(){

  n=rd();

  for(R ll i=1;i<=n;++i) ++s[rd()];

  dfs(s[1],s[2],s[3],s[4],s[5],6);

  printf("%lld\n",f[s[1]][s[2]][s[3]][s[4]][s[5]][6]);

  return 0;

}

巴特西

[ SCOI 2008 ] 着色方案

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章