NC20265 [SCOI2008]着色方案

[SCOI2008]着色方案

https://ac.nowcoder.com/acm/problem/20265

[SCOI2008]着色方案

题目地址：

https://ac.nowcoder.com/acm/problem/20265

基本思路：

必须吐槽一下，怎么题目又没有写数据范围QAQ，这题没数据范围写不了啊。

$1 <= k <= 15, 1 <= ci <= 5$

考虑 $dp$ ，但是如果我们用每种颜色的油漆作为维度 $dp$ 显然不太行，
因此我们关注 $1 <= ci <= 5$ ,考虑到每一种油漆，如果能涂的木块的数量相同的话，其实是等效的，
所以我们用 $dp[a][b][c][d][e][nxt]$ 分别表示还剩下 $1,2,3,4,5$ 次使用次数的油漆的数量为 $a,b,c,d,e$ ，上一次我们涂的是使用次数剩余为 $nxt$ 的油漆，然后注意我们每次转移时因为不能连续两块相同颜色，所以如果上一次用的还能涂 $i$ 次的油漆，那么当前就有一种还能够涂 $i-1$ 次的油漆无用。
由于并没有明显的顺序递推关系，所以我们考虑用记忆化搜索模拟 $dp$ ,具体转移方程比较长，见代码。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int mod = 1e9 + 7;
int dp[16][16][16][16][16][6];// 使用次数分别为 1,2,3,4,5的油漆的数量，和上一次使用的是还能用几次的油漆;
int dfs(int a,int b,int c,int d,int e,int nxt) {
  if (dp[a][b][c][d][e][nxt] != 0) return dp[a][b][c][d][e][nxt]; // 记忆化搜索过程,计算过就直接返回答案;
  if (a + b + c + d + e == 0) return dp[a][b][c][d][e][nxt] = 1;
  int res = 0;
  // 转移方程里前面括号中减去的那部分,是为了去除了连续两块颜色相同的情况;
  if (a > 0) res += 1ll * (a - (nxt == 2)) * dfs(a - 1, b, c, d, e, 1) % mod; res %= mod;
  if (b > 0) res += 1ll * (b - (nxt == 3)) * dfs(a + 1, b - 1, c, d, e, 2) % mod; res %= mod;
  if (c > 0) res += 1ll * (c - (nxt == 4)) * dfs(a, b + 1, c - 1, d, e, 3) % mod; res %= mod;
  if (d > 0) res += 1ll * (d - (nxt == 5)) * dfs(a, b, c + 1, d - 1, e, 4) % mod; res %= mod;
  if (e > 0) res += 1ll * e * dfs(a, b, c, d + 1, e - 1, 5) % mod;
  return dp[a][b][c][d][e][nxt] = res % mod;
}
int memo[6]; // 每种使用次数的油漆的数量;
signed main() {
  int k = read();
  rep(i,1,k) {
    int x = read();
    memo[x]++;
  }
  int ans = dfs(memo[1],memo[2],memo[3],memo[4],memo[5],0);
  cout << ans << '\n';
  return 0;
}