状压dp——涂抹果酱
这道题的状态有三种红绿蓝。
所以按一般的状压dp的做法,不难想到我们可以用三进制的形式来储存每一行的状态。
但因为K行蛋糕已经涂好,所以应该先判断K行蛋糕是否符合要求。按常规思路处理时,不要忘记考虑当i=k这种情况就可以了。
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=1e6,maxn=1e4+10;
int n,m,k,a,cnt,f[maxn][250],t,st[250],pos,ans;
int jud(int x)
{
int tmp=0x3f;
for(int i=1;i<=m;i++)
{
if(tmp==x%3) return 0;
tmp=x%3;x=x/3;
}
return 1;
}
int judge(int x,int y)
{
for(int i=1;i<=m;i++)
{
if(x%3==y%3) return 0;
x=x/3;y=y/3;
}
return 1;
}
int main()
{
cin>>n>>m>>k;cnt=1;
for(int x,i=1;i<=m;i++)
{
cin>>x;x--;cnt*=3;
a=a*3+x;
}
for(int i=0;i<cnt;i++)
if(jud(i)) st[++t]=i;
for(int i=1;i<=t;i++)
{
if(a==st[i])
{
pos=i;break;
}
}
if(!pos) {cout<<0;return 0;}
for(int i=1;i<=n;i++)
if(i==k)
if(i==1) f[i][pos]=1;
else for(int j=1;j<=t;j++)
{
if(judge(st[j],a))
f[i][pos]=(f[i][pos]+f[i-1][j])%mod;
}
else
for(int j=1;j<=t;j++)
{
if(i==1) f[i][j]=1;
else for(int l=1;l<=t;l++)
{
if(judge(st[j],st[l]))
f[i][j]=(f[i][j]+f[i-1][l])%mod;
}
}
for(int i=1;i<=t;i++)
ans=(ans+f[n][i])%mod;
cout<<ans;
return 0;
}