bzoj1079 着色方案记忆化搜索（dp）

题目传送门

题目大意：

　　有k种颜色，每个颜色ci可以涂个格子，要求相邻格子颜色不能一样，求方案数。ci<=5,k<=15.

思路：

　　题目里最重要的限制条件是相邻格子颜色不能相同，也就是当前格子只和上一个格子有关，那么对于还剩相同个数的颜色，如果都和上一个颜色不一样的话，那么这几种颜色都是一样的。如果某一种颜色和上一个颜色一样，那这个不算就可以了。

　　所以f[a][b][c][d][e][last]表示，还剩1次的颜色有a个，2两次颜色有b个，3次的颜色有c个，4次的颜色d个，5次的颜色e个，上一次用的颜色属于last的情况数量，1=<last<=5.

　　转移方程就倒着搜就可以了，没搜过的状态标记为-1，搜过的状态直接返回，看代码比较好理解。

　　需要注意的点是，比如上一次用的是还剩5个的颜色last，那么对于这一次来说，所有4个的颜色中有一种是从5个减少而来的，和上一个颜色一样，所以这个情况不能计算。

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

ll f[][][][][][];

ll p=;

int k;

ll sum[];

ll dp(ll a,ll b,ll c,ll d,ll e,int last){

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

        f[][][][][][last]=;

        return ;

    }

    if(f[a][b][c][d][e][last]!=-){

        return f[a][b][c][d][e][last];

    }

    ll tot=;

    if(a>){

        tot+=(a-(last==))*dp(a-,b,c,d,e,);

        tot%=p;

    }

    if(b>){

        tot+=(b-(last==))*dp(a+,b-,c,d,e,);

        tot%=p;

    }

    if(c>){

        tot+=(c-(last==))*dp(a,b+,c-,d,e,);

        tot%=p;

    }

    if(d>){

        tot+=(d-(last==))*dp(a,b,c+,d-,e,);

        tot%=p;

    }

    if(e>){

        tot+=(e)*dp(a,b,c,d+,e-,);

        tot%=p;

    }

    return f[a][b][c][d][e][last]=tot%p;

}

int main(){

    cin>>k;

    for(int i=;i<=k;i++)

    {

        int x;

        scanf("%d",&x);

        sum[x]++;

    }

    CLR(f,-);

    ll ans=dp(sum[],sum[],sum[],sum[],sum[],);

    cout<<ans<<endl;

}

1079: [SCOI2008]着色方案

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2986 Solved: 1792
[Submit][Status][Discuss]

Description

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

Input

　　第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。

Output

　　输出一个整数，即方案总数模1,000,000,007的结果。

Sample Input

3
1 2 3

Sample Output

HINT

100%的数据满足：1 <= k <= 15, 1 <= ci <= 5

bzoj1079 着色方案 记忆化搜索（dp）