状压DP【p1879】[USACO06NOV]玉米田Corn Fields

下面的\(n,m\)为\(n\)行\(m\)列,与题目描述不符.

难得做起了状压DP的题

表示有点懵.但是莫名其妙地A了 emmm

\(f[i]\)代表第\(i\)行的状态.就是输入的状态,这个东西的话就直接算就好了.

\[(f[i]<<=1)|=x
\]

初始化：\(dp[0][0]=1\)

那么我们需要枚举每一行,再枚举状态\(j\)判断当前行的状态\(f[i]\)是否会包含状态\(j\),即合法与否.

判断不能有相临的话,直接写一个函数即可

\[return ((state＆ (state>>1))==0 \ and\ (state＆(state<<1))==0);
\]

这里就不多解释了.

然后再枚举上一行状态\(k\)是否与当前状态\(j\)不相邻.即上下\(＆\)起来为0。

(这就涉及到了\(＆\)的性质,两边为\(True\)才为\(True\))

\[ans=\sum_{i=0}^{(1<<m)-1}f[n][i]
\]

时间复杂度\(O(n \times 2^{2 \times m})\)

代码

#include<cstdio>

#include<cctype>

#define mod 100000000

#define R register

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int res[15][15],f[18],n,m,dp[18][1<<15],ans;

inline bool ok(int state)

{

	return ((state&(state>>1))==0 and (state&(state<<1))==0);

}

int main()

{

	in(n),in(m);

	for(R int i=1;i<=n;i++)

		for(R int j=1,x;j<=m;j++)

		{

			in(x);

			(f[i]<<=1)|=x;

		}

	int state=(1<<m)-1;

	dp[0][0]=1;

	for(R int i=1;i<=n;i++)

		for(R int j=0;j<=state;j++)

			if(ok(j) and (f[i]&j)==j)

				for(R int k=0;k<=state;k++)

					if((k&j)==0)

						(dp[i][j]+=dp[i-1][k])%=mod;

	for(R int i=0;i<=state;i++)

		(ans+=dp[n][i])%=mod;

	printf("%d",ans%mod);

}