E – 着色方案 (dp)

  • 2019-02-10
  • 0
  • 0

题目链接:https://cn.vjudge.net/contest/281963#problem/E

题意:n个木板,k种颜料,每种颜料有c[i]个,输出相邻木板颜色不同的方案数。

思路:dp,也可以说是记忆化搜索。
dp[a1][a2][a3][a4][a5][last]
a1:颜料数目还剩下1个的还有多少种
a2,a3,a4,a5类似
last代表上一次选择了颜料剩下多少个
详情看代码:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mod=1e9+7;
ll a[25];
ll dp[16][16][16][16][16][16];

ll dfs(ll a1,ll a2,ll a3,ll a4,ll a5,ll last)
{
    if(dp[a1][a2][a3][a4][a5][last])return dp[a1][a2][a3][a4][a5][last];
    if(a1+a2+a3+a4+a5==0)return dp[a1][a2][a3][a4][a5][last]=1;
    ll ans=0;
    if(a1)
    {
        if(last==2)ans+=(a1-1)*dfs(a1-1,a2,a3,a4,a5,1);
        else ans+=a1*dfs(a1-1,a2,a3,a4,a5,1);
        ans%=mod;
    }
    if(a2)
    {
        if(last==3)ans+=(a2-1)*dfs(a1+1,a2-1,a3,a4,a5,2);
        else ans+=a2*dfs(a1+1,a2-1,a3,a4,a5,2);
        ans=ans%mod;
    }
    if(a3)
    {
        if(last==4)ans+=(a3-1)*dfs(a1,a2+1,a3-1,a4,a5,3);
        else ans+=a3*dfs(a1,a2+1,a3-1,a4,a5,3);
        ans=ans%mod;
    }
    if(a4)
    {
        if(last==5)ans+=(a4-1)*dfs(a1,a2,a3+1,a4-1,a5,4);
        else ans+=a4*dfs(a1,a2,a3+1,a4-1,a5,4);
        ans=ans%mod;
    }
    if(a5)
    {
        ans+=(a5)*dfs(a1,a2,a3,a4+1,a5-1,5);
        ans=ans%mod;
    }
    return dp[a1][a2][a3][a4][a5][last]=ans%mod;
}

int main()
{
    //ios::sync_with_stdio(false);
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        a[x]++;
    }
    ll ans=dfs(a[1],a[2],a[3],a[4],a[5],0);
    printf("%lld\n",ans%mod);
    return 0;
}

评论

还没有任何评论,你来说两句吧