BZOJ1079或洛谷2476 [SCOI2008]着色方案

一道记忆化搜索

BZOJ原题链接

洛谷原题链接

发现对于能涂木块数量一样的颜色在本质上是一样的，所以可以直接压在一个状态，而这题的数据很小，直接暴力开\(6\)维。
定义\(f[a][b][c][d][e][la]\)，\(a\)表示能涂\(1\)个木块的颜色总数，\(b\)表示能涂\(2\)个木块的颜色总数，\(c,d,e\)同理，\(la\)表示上次涂的颜色是能涂\(la\)个木块的。
然后考虑状态转移。如果用能涂\(1\)个木块的颜色去涂，则状态由\((a-(la==2))*f[a-1][b][c][d][e][1]\)转移来，因为有\(a\)种颜色，每一种都可以涂，所以要乘上\(a\)，但注意当前状态的\(la=2\)的情况，就是说这个状态是由可以涂\(2\)个木块的颜色转移过来的，这时原来能涂\(2\)个木块的颜色变成只能涂\(1\)个了，题目要求相邻木块不能涂同一颜色，所以要将\(a\)减去\(1\)。对于用能涂\(2\)个木块的颜色去涂，则状态由\((b-(la==3))*f[a+1][b-1][c][d][e][2]\)转移来，其他同理得。
显然使用记忆化搜索更好打。

#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 16;
const int mod = 1e9 + 7;
ll f[N][N][N][N][N][6];
int co[6];
int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c<'0' || c>'9'; c = getchar())
        p = (c == '-' || p) ? 1 : 0;
    for (; c >= '0'&&c <= '9'; c = getchar())
        x = x * 10 + (c - '0');
    return p ? -x : x;
}
ll dp(int a, int b, int c, int d, int e, int la)
{
    ll s = 0, &k = f[a][b][c][d][e][la];
    if (k)
        return k;
    if (!(a | b | c | d | e))
        return 1;
    if (a)
        s += 1LL * (a - (la == 2))*dp(a - 1, b, c, d, e, 1);
    if (b)
        s += 1LL * (b - (la == 3))*dp(a + 1, b - 1, c, d, e, 2);
    if (c)
        s += 1LL * (c - (la == 4))*dp(a, b + 1, c - 1, d, e, 3);
    if (d)
        s += 1LL * (d - (la == 5))*dp(a, b, c + 1, d - 1, e, 4);
    if (e)
        s += 1LL * e*dp(a, b, c, d + 1, e - 1, 5);
    k = s % mod;
    return k;
}
int main()
{
    int i, n;
    n = re();
    for (i = 1; i <= n; i++)
        co[re()]++;
    printf("%lld", dp(co[1], co[2], co[3], co[4], co[5], 0));
    return 0;
}

ps：因为我用的是\(VS\)，所以代码会自动补空格，而我本来的风格是没有空格的。

BZOJ1079或洛谷2476 [SCOI2008]着色方案

原文：https://www.cnblogs.com/Iowa-Battleship/p/9526257.html