[SCOI 2008] 着色方案

[题目链接]

          https://www.lydsy.com/JudgeOnline/problem.php?id=1079

[算法]

        f[c1][c2][c3][c4][c5][pre]表示有c1种颜色可以涂1个木块，c2中颜色可以涂2个木块,.....,上一次的颜色可以涂pre个木块

        记忆化搜索即可

[代码]

          

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;

int i,k,x;
int cnt[10];
int f[16][16][16][16][16][6];

inline int dp(int c1,int c2,int c3,int c4,int c5,int pre)
{
    if (c1 < 0 || c2 < 0 || c3 < 0 || c4 < 0 || c5 < 0) return 0;
    if (!c1 && !c2 && !c3 && !c4 && !c5) return f[c1][c2][c3][c4][c5][pre] = 1;
    if (f[c1][c2][c3][c4][c5][pre] != -1) return f[c1][c2][c3][c4][c5][pre];
    f[c1][c2][c3][c4][c5][pre] = 0;
    if (pre == 2) f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * (c1 - 1) * dp(c1 - 1,c2,c3,c4,c5,1)) % P;
    else  f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * c1 * dp(c1 - 1,c2,c3,c4,c5,1)) % P;
    if (pre == 3) f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * (c2 - 1) * dp(c1 + 1,c2 - 1,c3,c4,c5,2)) % P;
    else f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * c2 * dp(c1 + 1,c2 - 1,c3,c4,c5,2)) % P;
    if (pre == 4) f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * (c3 - 1) * dp(c1,c2 + 1,c3 - 1,c4,c5,3)) % P;
    else f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * c3 * dp(c1,c2 + 1,c3 - 1,c4,c5,3)) % P;
    if (pre == 5) f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * (c4 - 1) * dp(c1,c2,c3 + 1,c4 - 1,c5,4)) % P;
    else f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * c4 * dp(c1,c2,c3 + 1,c4 - 1,c5,4)) % P;
    f[c1][c2][c3][c4][c5][pre] = (f[c1][c2][c3][c4][c5][pre] + 1ll * c5 * dp(c1,c2,c3,c4 + 1,c5 - 1,5)) % P;
    return f[c1][c2][c3][c4][c5][pre];
}

int main()
{
    
    scanf("%d",&k);
    for (i = 1; i <= k; i++)
    {
        scanf("%d",&x);
        cnt[x]++;
    }
    memset(f,255,sizeof(f));
    printf("%d
",dp(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],0));
    
    return 0;
}