M_sea

洛谷2476 [SCOI2008]着色方案
LuoguBZOJ分析注意到 $c_i\leq 5$。设 $f[c1][c2][c3][c4][c5][last]...
扫描右侧二维码阅读全文
28
2019/02

洛谷2476 [SCOI2008]着色方案

Luogu

BZOJ

分析

注意到 $c_i\leq 5$。

设 $f[c1][c2][c3][c4][c5][last]$ 表示还能涂 $1$ 个格子的油漆有 $c1$种,还能涂 $2$ 个格子的油漆有 $c2$种,……,上一次用的是能涂 $last$ 个格子的油漆。

状态转移方程就比较容易了,不会的戳这里

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1000000007;

int n;
int t[6];
int f[16][16][16][16][16][6];

inline int dfs(int c1,int c2,int c3,int c4,int c5,int last) {
    if (f[c1][c2][c3][c4][c5][last])
        return f[c1][c2][c3][c4][c5][last];
    int res=0;
    if (c1)
        res=(res+1ll*(c1-(last==2))*dfs(c1-1,c2,c3,c4,c5,1))%mod;
    if (c2)
        res=(res+1ll*(c2-(last==3))*dfs(c1+1,c2-1,c3,c4,c5,2))%mod;
    if (c3)
        res=(res+1ll*(c3-(last==4))*dfs(c1,c2+1,c3-1,c4,c5,3))%mod;
    if (c4)
        res=(res+1ll*(c4-(last==5))*dfs(c1,c2,c3+1,c4-1,c5,4))%mod;
    if (c5)
        res=(res+1ll*c5*dfs(c1,c2,c3,c4+1,c5-1,5))%mod;
    return f[c1][c2][c3][c4][c5][last]=res;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) ++t[read()];
    for (re int i=1;i<=5;++i) f[0][0][0][0][0][i]=1;
    printf("%d\n",dfs(t[1],t[2],t[3],t[4],t[5],0));
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 03 PM

发表评论