【AHOI2013复仇】SCOI2008 着色方案

Posted on 2012-10-24 14:59 Mato_No1 阅读(502) 评论(0)  编辑 收藏 引用 所属分类: 动态规划SCOI
原题地址
首先,看这么小的范围就知道,数学方法肯定搞不了……又想不到其它模型……只能用状压硬搞了囧……
问题是,5^15稳T,如果能倒过来,15^5,就不会T了。
可以发现,C值相同的颜色本质上是一样的……因此,只需要保存目前C值为1、2、3、4、5的颜色各有多少种就行了囧……(当然在过程中还会出现C值为0的,即用完的颜色,不过0、1、2、3、4、5的和是颜色总数,而且从下面可以看出,C值为0的确实“木有用”);
设F[s1][s2][s3][s4][s5][v]为涂完前若干个木块(这个个数可以通过s1~s5算出,不过我们并不需要它囧……)后,C值为1~5的颜色各有s1~s5种,且这若干个中的最后一个涂的颜色还剩的C值为v(显然0<=v<=4)。
边界:F[S[1]][S[2]][S[3]][S[4]][S[5]][0]=1,其余为0(S[i]为一开始C值为i的颜色种数)。
计算F时,前推后(注意顺序,是按照S[5]逆序最先,再依次是S[4]~S[1],都是逆序,v可任意定序),枚举下一个木块的颜色是现在还剩多少的,如果它与目前的这个(最后一个)剩的相同,则要减1,否则不减。具体的方程见代码。
注意细节:枚举F的s1~s5下标时,都要N(颜色总数)开始枚举,因为过程中某些s值会增加;

本题的启示就是,在设计状压DP的时候,如果正着来不行,可以反着来,或许就能设计出符合要求的解法。

代码:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int n = 5, MAXM = 16, MOD = 1000000007;
int m, S[n + 1];
ll F[MAXM][MAXM][MAXM][MAXM][MAXM][n], res;
void init()
{
    scanf(
"%d"&m); int x;
    re(i, m) {scanf(
"%d"&x); S[x]++;}
}
void solve()
{
    F[S[
1]][S[2]][S[3]][S[4]][S[5]][0= 1int tmp;
    rre3(i5, m, 
0) rre3(i4, m, 0) rre3(i3, m, 0) rre3(i2, m, 0) rre3(i1, m, 0) re(v, n)
        
if (F[i1][i2][i3][i4][i5][v]) {
            
if (i1) {
                
if (v == 1) tmp = i1 - 1else tmp = i1;
                
if (tmp) {
                    F[i1 
- 1][i2][i3][i4][i5][0+= tmp * F[i1][i2][i3][i4][i5][v];
                    F[i1 
- 1][i2][i3][i4][i5][0%= MOD;
                }
            }
            
if (i2) {
                
if (v == 2) tmp = i2 - 1else tmp = i2;
                
if (tmp) {
                    F[i1 
+ 1][i2 - 1][i3][i4][i5][1+= tmp * F[i1][i2][i3][i4][i5][v];
                    F[i1 
+ 1][i2 - 1][i3][i4][i5][1%= MOD;
                }
            }
            
if (i3) {
                
if (v == 3) tmp = i3 - 1else tmp = i3;
                
if (tmp) {
                    F[i1][i2 
+ 1][i3 - 1][i4][i5][2+= tmp * F[i1][i2][i3][i4][i5][v];
                    F[i1][i2 
+ 1][i3 - 1][i4][i5][2%= MOD;
                }
            }
            
if (i4) {
                
if (v == 4) tmp = i4 - 1else tmp = i4;
                
if (tmp) {
                    F[i1][i2][i3 
+ 1][i4 - 1][i5][3+= tmp * F[i1][i2][i3][i4][i5][v];
                    F[i1][i2][i3 
+ 1][i4 - 1][i5][3%= MOD;
                }
            }
            
if (i5) {
                F[i1][i2][i3][i4 
+ 1][i5 - 1][4+= i5 * F[i1][i2][i3][i4][i5][v];
                F[i1][i2][i3][i4 
+ 1][i5 - 1][4%= MOD;
            }
        }
    res 
= F[0][0][0][0][0][0];
}
void pri()
{
    cout 
<< res << endl;
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理