狀壓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;
}