您的位置: 首页  >  IT文章  >  [SCOI2008]着色方案 题目大意: 基本思路: code:

[SCOI2008]着色方案 题目大意: 基本思路: code:

分类: IT文章 • 2024-01-27 15:59:12

　　给你$k$种颜料,每种颜料有$c_{i}$份,每份颜料涂一块木板,求恰好用完所有颜料且相邻两木板颜色不同的涂色方案种数.($1leq kleq 15$,$1leq c_{i}leq 5$)

基本思路:

　　由于此题数据较小,考虑DP套组合数学,但重复dp运算量极大,考虑记忆化搜索优化.又因为每种颜料至多5份,类比乌龟棋,我们可以开一个五维数组存储状态,但考虑相邻木板颜色不同,于是再加一个维度last,表示我们当前的状态是由上次涂了能够涂last次的状态转移过来,所以可以用组合减掉不合法方案.思路有点抽象,下面来点形象(更抽象)的状态转移方程

　　$ifleft(a ight)$ $res+=left(a-left(last==2 ight) ight)*dfsleft(a-1,b,c,d,e,1 ight);$

　　$ifleft(b ight)$ $res+=left(b-left(last==3 ight) ight)*dfsleft(a+1,b-1,c,d,e,2 ight);$

　　$ifleft(c ight)$ $res+=left(c-left(last==4 ight) ight)*dfsleft(a,b+1,c-1,d,e,3 ight);$

　　$ifleft(d ight)$ $res+=left(d-left(last==5 ight) ight)*dfsleft(a,b,c+1,d-1,e,4 ight);$

　　$ifleft(e ight)$ $res+=e*dfsleft(a,b,c,d+1,e-1,5 ight);$

　　其中$k-left(last==x ight)$表示上一次转移的时候若用了剩余x种的颜料,那现在就得减掉1(即那种用掉的)

code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define mod 1000000007
#define R register
#define next exnt
#define debug puts("mlg")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writesp(ll x);
inline void writeln(ll x);
ll k;
ll f[16][16][16][16][16][6];
ll num[16];
ll ans;
inline ll dfs(ll a,ll b,ll c,ll d,ll e,ll last){
    if(f[a][b][c][d][e][last]!=-1) return f[a][b][c][d][e][last];
    if(a+b+c+d+e==0)return 1;
    ll res=0;
    if(a) res+=(a-(last==2))*dfs(a-1,b,c,d,e,1);    
    if(b) res+=(b-(last==3))*dfs(a+1,b-1,c,d,e,2);
    if(c) res+=(c-(last==4))*dfs(a,b+1,c-1,d,e,3);
    if(d) res+=(d-(last==5))*dfs(a,b,c+1,d-1,e,4);
    if(e) res+=e*dfs(a,b,c,d+1,e-1,5);
    return f[a][b][c][d][e][last]=res%mod;
}
int main(){
    k=read();
    for(R ll i=1;i<=k;i++){
        ++num[read()];
    }
    memset(f,-1,sizeof f);
    writeln(dfs(num[1],num[2],num[3],num[4],num[5],0));
}
inline ll read(){
    ll x=0,t=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*t;
}
inline void write(ll x){
    if(x<0){putchar('-');x=-x;}
    if(x<=9){putchar(x+'0');return;}
    write(x/10);putchar(x%10+'0');
}
inline void writesp(ll x){
    write(x);putchar(' ');
}
inline void writeln(ll x){
    write(x);putchar('
');
}

相关推荐