bzoj2331:[SCOI2011]地板(插头DP)

Author Avatar
Sakits 8月 02, 2018

题解

  插头DP这种完美匹配问题感觉就是对每种可填的东西都分成不同的状态,可填的东西内部可能也需要分一下状态,然后瞎转移就好了…
  这题把还未拐角的设为11,已经拐角了的设为22就好了。
  第一种情况是左上都无插头,那么可以下右都插一个22或者选一个插一个11
  第二种情况是只有一边有11插头,那么可以继续延伸为11也可以拐角插头变成22
  第三种情况是只有一边有22插头,那么可以继续延伸为22也可以终止变成00
  第四种情况是左上都有11插头,这个时候合并成为一个LL,状态变为00
  其他情况都不合法。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define MOD(x) ((x)>=mod?(x)-mod:(x))
#define ll long long
using namespace std;
const int maxn=1000010, inf=1e9, hashmod=23333, mod=20110520;
struct ctdp
{
	int tot;
	int last[hashmod], sta[maxn], pre[maxn], ans[maxn];
	void init()
	{
		tot=0;
		memset(last, 0, sizeof(last));
	}
	void add(int x, int y){sta[++tot]=y; pre[tot]=last[x]; last[x]=tot;}
	void upd(int st, int delta)
	{
		int hs=st%hashmod;
		for(int i=last[hs];i;i=pre[i])
		if(sta[i]==st)
		{
			ans[i]=MOD(ans[i]+delta);
			return;
		}
		add(hs, st); ans[tot]=delta;
	}
}f[2];
int n, m;
int mp[233][233];
char s[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline int encode(int st)
{
	int ans=0;
	for(int i=0;i<=m;i++) ans=ans*10+(st&3), st>>=2;
	return ans;
}

inline void DP()
{
	int pos=0; f[pos].init(); f[0].upd(0, 1);
	for(int i=1;i<=n;i++)
	{
		pos^=1; f[pos].init();
		for(int j=1;j<=f[pos^1].tot;j++)
		f[pos].upd(f[pos^1].sta[j]<<2, f[pos^1].ans[j]);
		for(int j=1;j<=m;j++)
		{
			pos^=1; f[pos].init();
			for(int k=1;k<=f[pos^1].tot;k++)
			{
				int st=f[pos^1].sta[k], ans=f[pos^1].ans[k];
				int lt=(st>>((j-1)<<1))&3, up=(st>>(j<<1))&3;
				st^=(lt<<((j-1)<<1))|(up<<(j<<1));
				if(mp[i][j])
				{
					if(!lt && !up)
					{
						if(mp[i+1][j] && mp[i][j+1]) f[pos].upd(st|(2<<((j-1)<<1))|(2<<(j<<1)), ans);
						if(mp[i+1][j]) f[pos].upd(st|(1<<((j-1)<<1)), ans);
						if(mp[i][j+1]) f[pos].upd(st|(1<<(j<<1)), ans);
					}
					if(lt+up==1)
					{
						if(mp[i+1][j]) f[pos].upd(st|((1+(up==0))<<((j-1)<<1)), ans);
						if(mp[i][j+1]) f[pos].upd(st|((1+(lt==0))<<(j<<1)), ans);
					}
					if((!lt && up==2) || (lt==2 && !up))
					{
						if(up && mp[i+1][j]) f[pos].upd(st|(2<<((j-1)<<1)), ans);
						if(lt && mp[i][j+1]) f[pos].upd(st|(2<<(j<<1)), ans);
						f[pos].upd(st, ans);
					}
					if(lt==1 && up==1) f[pos].upd(st, ans);
				}
				else if(!lt && !up) f[pos].upd(st, ans);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=f[pos].tot;i++)
	if(!f[pos].sta[i]) ans=MOD(ans+f[pos].ans[i]);
	printf("%d\n", ans);
}
 
int main()
{
	read(n); read(m);
	if(n>=m)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%s", s+1);
			for(int j=1;j<=m;j++)
			mp[i][j]=(s[j]=='_');
		}
	}
	else
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%s", s+1);
			for(int i=1;i<=m;i++)
			mp[i][j]=(s[i]=='_');
		}
		swap(n, m);
	}
	DP();
}