BZOJ1079 [SCOI2008]着色方案 动态规划

时间：2021-08-07 08:56:59

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1079

题目概括

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

题解

　　一开始想状压dp，压每种颜色的剩余数。

　　发现要超时。

　　访问了hzwer大佬的博客，立刻恍然大悟。

　　我们可以压每种剩余数的颜色个数！

　　具体：

　　dp[a][b][c][d][e][t]表示剩余1的颜色有a个，剩余2的颜色有b个，剩余3的颜色有c个，剩余4的颜色有d个，剩余5的颜色有e个，之前选择的那种颜色现在还剩t的方案总数。

　　那么复杂度为165×6≈6500000，应该不会超时了。

　　记忆化dfs比较好写，所以写了记忆化dfs。

代码

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

typedef long long LL;

const LL mod=;

int k,tot[];

LL dp[][][][][][];

LL DP(int a,int b,int c,int d,int e,int t){

    if (dp[a][b][c][d][e][t]!=-)

        return dp[a][b][c][d][e][t];

    if (a+b+c+d+e==)

        return dp[a][b][c][d][e][t]=;

    int A=a-(t==),B=b-(t==),C=c-(t==),D=d-(t==),E=e;

    LL &res=dp[a][b][c][d][e][t];

    res=;

    if (a)

        res+=A*DP(a-,b,c,d,e,);

    if (b)

        res+=B*DP(a+,b-,c,d,e,);

    if (c)

        res+=C*DP(a,b+,c-,d,e,);

    if (d)

        res+=D*DP(a,b,c+,d-,e,);

    if (e)

        res+=E*DP(a,b,c,d+,e-,);

    return res%=mod;

}

int main(){

    memset(dp,-,sizeof dp);

    memset(tot,,sizeof tot);

    scanf("%d",&k);

    for (int i=,a;i<=k;i++){

        scanf("%d",&a);

        tot[a]++;

    }

    printf("%lld",DP(tot[],tot[],tot[],tot[],tot[],));

    return ;

}

相关文章