当前位置:网站首页>[SCOI2008]着色方案 递推 记忆化搜索

[SCOI2008]着色方案 递推 记忆化搜索

2021-07-23 04:21:23 mb60dd3a6942180

我们发现 $c_{i}$ 和 $k$ 的规模非常小
我们还发现每种颜色的位置是不必知道的,只要这种颜色和相邻的颜色种类不同即可。
定义状态 $f[a][b][c][d][e][last]$,代表有 $a$ 个还可以放 1 个,$b$ 个可以放 2 个,$c$ 个可以放3个......上一个状态最后一个放的数是可以放 $last$ 个的种类。

考虑记忆化搜索:
$f[a][b][c][d][e][last]+=f[a-1][b][c][d][e][1]*(a-(last==2))$
考虑当前放可以放1个的颜色,那么可放的颜色种类为 $a$ 个,但如果上一个状态中的最后一个放的种类为 2 的话它对当前状态中 $a$ 会贡献1,那么我们就要将这个 1 剪掉,其余情况同理。

 

Code:

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxn=16;
const ll mod=1000000007;
using namespace std;
void setIO(string a){
    freopen((a+".in").c_str(),"r",stdin);
}
ll f[maxn][maxn][maxn][maxn][maxn][6];
int t[maxn];
ll dp(int a,int b,int c,int d,int e,int 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 f[a][b][c][d][e][last]=1;
    ll res=0;
    if(a)  res+=(a-(last==2))*dp(a-1,b,c,d,e,1)%mod;
    if(b)  res+=(b-(last==3))*dp(a+1,b-1,c,d,e,2)%mod;
    if(c)  res+=(c-(last==4))*dp(a,b+1,c-1,d,e,3)%mod;
    if(d)  res+=(d-(last==5))*dp(a,b,c+1,d-1,e,4)%mod;
    if(e)  res+=e*dp(a,b,c,d+1,e-1,5)%mod;
    f[a][b][c][d][e][last]=res%mod;
    return res%mod;
}
int main(){
    //setIO("input");
    memset(f,-1,sizeof(f));
    int n,x; 
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>x; 
        ++t[x];
    }
    cout<<dp(t[1],t[2],t[3],t[4],t[5],0)-1;
    return 0;
}

       
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.

  

 
 

版权声明
本文为[mb60dd3a6942180]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15291195/3008722