题解 P2476 【[SCOI2008]着色方案】

**【解题思路】** 注意到题目中的信息 $1 \le ci \le 5$，同时 $c_i$ 相同的油漆本质上是相同的，于是我们令 $f[c_1][c_2][c_3][c_4][c_5][last]$ 表示当还能够涂 $1$ 个格子的油漆有 $c_1$ 种，还能够涂 $2$ 个格子的油漆有 $c_2$ 种……（以此类推）且按木块 $1$~$n$ 编号顺序涂，上一次涂的是能够涂 $last$ 个格子的油漆时的总方案数。 但这样还要判断是否相邻的情况，我们可以由此推出状态转移方程： $f[c_1][c_2][c_3][c_4][c_5][last] =$ $[c_1 - (last == 2)] * f[c_1 - 1][c_2][c_3[c_4][c_5][1] +$ $[c_2 - (last == 3)] * f[c_1 + 1][c_2 - 1][c_3][c_4][c_5][2] +$ $[c_3 - (last == 4)] * f[c_1][c_2 + 1][c_3 - 1][c_4][c_5][3] +$ $[c_4 - (last == 5)] * f[c_1][c_2][c_3 + 1][c_4 - 1][c_5][4] +$ $c_5 * f[c_1][c_2][c_3][c_4 + 1][c_5 - 1][5]$ 那么这是什么意思呢，显然方案数 $f$ 可以由下一次涂能够涂 $i (1 \le i \le 5)$ 个格子的油漆的方案数倒推转移过来，且涂完以后还能够涂 $i$ 个格子的油漆种数 $c_i - 1$，还能够涂 $i - 1$ 个格子的油漆种数 $c_{i-1} + 1$，表示这种油漆涂了 $1$ 个格子。 回到我们所说的相邻情况，假设上一次用的是可以涂 $last$ 个格子的油漆，那么上一次用完后，那种油漆就只可以涂 $last - 1$ 个格子了，那么这一次涂油漆的时候就不能再选可以涂 $last - 1$ 个格子的油漆的一种，因为这种上次已经用过了，且相同的油漆不能相邻。 考虑到方案数 $f$ 倒推而来，且有多种情况的转移，且每种情况又有无数多的分支，我们使用**记忆化搜索**。 记忆状态来优化时间效率，令搜索边界为 $f[0][0][0][0][0][last (1 \le last \le 5)] = 1$，即全部涂完方案数为 $1$，即可求出答案。 **【AC代码】** ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int Maxn = 0x3f3f3f3f, N = 16; const ll Mod = 1000000007; ll f[N][N][N][N][N][6], res; int n, m, x, num[6]; inline int get() { char ch; bool f = false; int res = 0; while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); if (ch == '-') f = true; else res = ch - '0'; while ((ch = getchar()) >='0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0'; return f? ~res + 1 : res; } inline void put(ll x) { if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) put(x / 10); putchar(x % 10 + 48); } inline ll Dfs(const int c1, const int c2, const int c3, const int c4, const int c5, const int lst) { if (f[c1][c2][c3][c4][c5][lst]) return f[c1][c2][c3][c4][c5][lst]; ll res = 0; if (c1) res = (res + (c1 - (lst == 2)) * Dfs(c1 - 1, c2, c3, c4, c5, 1)) % Mod; if (c2) res = (res + (c2 - (lst == 3)) * Dfs(c1 + 1, c2 - 1, c3, c4, c5, 2)) % Mod; if (c3) res = (res + (c3 - (lst == 4)) * Dfs(c1, c2 + 1, c3 - 1, c4, c5, 3)) % Mod; if (c4) res = (res + (c4 - (lst == 5)) * Dfs(c1, c2, c3 + 1, c4 - 1, c5, 4)) % Mod; if (c5) res = (res + c5 * Dfs(c1, c2, c3, c4 + 1, c5 - 1, 5)) % Mod; return f[c1][c2][c3][c4][c5][lst]=res; } int main() { for (int i = 1; i <= 5; ++i) f[0][0][0][0][0][i] = 1; n = get(); for (int i = 1; i <= n; ++i) num[x = get()]++; return put(Dfs(num[1], num[2], num[3], num[4], num[5], 0)), 0; } ```