题意

Farmer John新买了一块长方形的牧场，这块牧场被划分成M列N行\((1 \leq M \leq 12, 1 \leq N \leq 12)\)，每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地的感觉，于是FJ不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。当然，FJ还没有决定在哪些土地上种草。作为一个好奇的农场主，FJ想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮FJ算一下这个总方案数。

分析

状压裸题。

就每行建状态\(f(i,s)\)表示\(i\)行种草状态为\(s\)的方案数即可。

看到Farmer John和他的奶牛的一般都是水题。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<algorithm>

#include<bitset>

#include<cassert>

#include<ctime>

#include<cstring>

#define rg register

#define il inline

#define co const

template<class T>il T read()

{

	rg T data=0;

	rg int w=1;

	rg char ch=getchar();

	while(!isdigit(ch))

	{

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

	{

		data=data*10+ch-'0';

		ch=getchar();

	}

	return data*w;

}

template<class T>T read(T&x)

{

	return x=read<T>();

}

using namespace std;

typedef long long ll;

co int MAXN=12,mod=100000000;

int m,n;

int mp[MAXN],f[MAXN][1<<MAXN];

int ans;

int add(int x,int y)

{

	x+=y;

	return x>=mod?x-mod:x;

}

void dp()

{

	for(int i=mp[0];i>=0;i=!i?-1:(i-1)&mp[0])

		if((i & (i >> 1)) == 0)

			f[0][i]=1;

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

		for(int j=mp[i-1];j>=0;j=!j?-1:(j-1)&mp[i-1])

			if(f[i-1][j])

				for(int k=mp[i];k>=0;k=!k?-1:(k-1)&mp[i])

					if((j & k) == 0 && (k & (k >> 1)) == 0)

						f[i][k]=add(f[i][k],f[i-1][j]);

	for(int i=mp[m-1];i>=0;i=!i?-1:(i-1)&mp[m-1])

		ans=add(ans,f[m-1][i]);

}

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	read(m);read(n);

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

		for(int j=0;j<n;++j)

			mp[i]=mp[i]<<1|read<int>();

	dp();

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

	return 0;

}

巴特西

BZOJ1725,POJ3254 [Usaco2006 Nov]Corn Fields牧场的安排

题意

分析

代码

最新文章

热门文章