HYSBZ 1079 着色方案

题意:
 有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂c[i]个木块。
所有油漆刚好足够涂满所有木块,即c[1]+c[2]+...+c[k]=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相邻木块颜色不同的着色方案。
题解:

#include <cstdio>
typedef long long LL;
const int Mod=1e9+7;
int x[6],n;
LL f[16][16][16][16][16][6];
bool vis[16][16][16][16][16][6];
LL DFS(int,int,int,int,int,int);

int main(){
        scanf("%d",&n);
        int tmp;
        for(int i=1;i<=n;i++)
                scanf("%d",&tmp),x[tmp]++;
        //按每种颜色的剩余次数分类,剩余次数相同的分在一类
        printf("%lld
",DFS(x[1],x[2],x[3],x[4],x[5],0));
        return 0;
}

LL DFS(int a,int b,int c,int d,int e,int last){
        if(vis[a][b][c][d][e][last])return f[a][b][c][d][e][last];
        if(a+b+c+d+e==0)return 1;
        LL tmp=0;
        //考虑枚举这次选哪种剩余次数的颜色,一共有多少个剩余这种次数的个数就有多少种选择
        if(a)tmp+=(a-(last==2))*DFS(a-1,b,c,d,e,1);
        //如果上次填的是颜色剩余次数为2的,意味着颜色中剩余次数为1的多了一个
        //那么这一次并不能再选这种颜色,这次可以选填1的就要少1
        if(b)tmp+=(b-(last==3))*DFS(a+1,b-1,c,d,e,2);
        if(c)tmp+=(c-(last==4))*DFS(a,b+1,c-1,d,e,3);
        if(d)tmp+=(d-(last==5))*DFS(a,b,c+1,d-1,e,4);
        if(e)tmp+=e*DFS(a,b,c,d+1,e-1,5);
        //显然不需要考虑6的情况
        tmp%=Mod;
        vis[a][b][c][d][e][last]=true;
        return f[a][b][c][d][e][last]=tmp;
}

原文地址:https://www.cnblogs.com/holy-unicorn/p/9510152.html