1079: [SCOI2008]着色方案

思路

　　首先是dp，如果直接用每个种颜色的剩余个数做状态的话，复杂度为5^15。

　　由于c<=5，所以用剩余数量的颜色的种类数做状态：f[a][b][c][d][e][last]表示剩余数量为1的颜色种类数，为2,3,4,5的。

　　转移时，如果上一次使用的是为4的，这次如果转移使用3的话，为了使相邻的不相同，则需要-1

　　最后一个转移写错了个地方，一直re...

代码

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 typedef long long LL;

 const LL mod = 1e9+;

 const int N = ;

 LL f[N][N][N][N][N][];

 int t[];

 LL dfs(int a,int b,int c,int d,int e,int last) {

     if ((a|b|c|d|e)==) return ;

     if (f[a][b][c][d][e][last]) return f[a][b][c][d][e][last];

     LL ans = ;

     if (a) ans += dfs(a-,b,c,d,e,)*(a-(last==));

     if (ans > mod) ans %= mod;

     if (b) ans += dfs(a+,b-,c,d,e,)*(b-(last==));

     if (ans > mod) ans %= mod;

     if (c) ans += dfs(a,b+,c-,d,e,)*(c-(last==));

     if (ans > mod) ans %= mod;

     if (d) ans += dfs(a,b,c+,d-,e,)*(d-(last==));

     if (ans > mod) ans %= mod;

     if (e) ans += dfs(a,b,c,d+,e-,)*e; //-

     if (ans > mod) ans %= mod;

     f[a][b][c][d][e][last] = ans;

     return ans;

 }

 int main() {

     int n;

     cin >> n;

     for (int a,i=; i<=n; ++i) {

         cin >> a;

         t[a] ++;

     }

     cout << dfs(t[],t[],t[],t[],t[],);

     return ;

 }

巴特西

1079: [SCOI2008]着色方案

最新文章

热门文章