LG1879 「USACO2006NOV」Corn Fields 状压DP

问题描述

LG1879

题解

设\(opt[i][j]\)代表前\(i\)行，且第\(i\)行状态为\(j\)的方案数。

枚举\(j\)，再枚举\(k\)，\(k\)为上一行的状态。

判断\(j,k\)能否共存（j&k==0）

计数转移即可。

必须加强位运算能力。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int mod=100000000;

int ans,n,m;

int a[14];

int opt[14][(1<<12)];

bool exist[(1<<12)];

int main(){

	read(n);read(m);

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

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

			read(x);a[i]=(a[i]<<1)+x;

		}

	}

	for(int i=0;i<(1<<m);i++){

		if(((i&(i<<1))==0)&&((i&(i>>1))==0)) exist[i]=1;

	}

	opt[0][0]=1;

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

		for(int j=0;j<(1<<m);j++){

			if(!exist[j]) continue;

			if((j&a[i])!=j) continue;

			for(int k=0;k<(1<<m);k++){

				if((j&k)==0) opt[i][j]=(opt[i][j]+opt[i-1][k])%mod;

			}

		}

	}

	for(int i=0;i<(1<<m);i++){

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

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

LG1879 「USACO2006NOV」Corn Fields 状压DP

问题描述

题解

必须加强位运算能力。

\(\mathrm{Code}\)

最新文章

热门文章