[poj3254]Corn Fields

Corn Fields poj3254

　　　　题目大意：给你一个n*m的地，每一块地可以种或不种，两块种过的地不能挨着，可以一块都不种，问所有的种地方案数。

　　　　注释：读入用0和1，1<=n,m<=12.

　　　　　　想法：这题和炮兵阵地特别像，比炮兵更简单。我们再度入的时候直接处理出当前行的地的不可种的情况。预处理出一行如果都能种的话所可能的方案数。此处需要满足的就是两块地不能挨着，通过打表我们可以发现这种情况最多只有377种情况(我们附上打表用的程序)

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

bool check(int x)//判断当前状态是否可行

{

	if(x&(x<<1)) return false;

	return true;

}

int cnt;

void before(int mid)//处理所有状态

{

	for(int i=0;i<(1<<mid);i++)

	{

		if(check(i)) cnt++;

	}

}

int main()

{

	int n;

	cin >> n;

	before(n);

	printf("%d\n",cnt);//输出所有可行状态数

	return 0;

}

　　　　　　然后，我们先预处理出第一行，怎么处理呢？其实map是0的情况，也就是读入数据的反码。我们对于一个状态只需要通过&上map对应的下标就可以判断当前数据是否合法。如果合法，dp[1][i]就是1。其中，dp[i][j]表示第 i 行状态为 j ，前 i 行能填充的方案数。转移时，我们通过外层松弛行数，内层枚举所有状态，用&判断即可。

　　　　最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mod 1000000000

using namespace std;

int dp[15][380];

int map[15];//存储的是反码

int str[380];//存储所有状态

// int sum[350];

int cnt;//状态数目

bool check(int x)//判断当前状态是否可行

{

	if(x&(x<<1)) return false;

	return true;

}

// int getSum(int x)

// {

// 	int ans=0;

// 	while(x>0)

// 	{

// 		if(x&1) ans++;

// 		x>>=1;

// 	}

// 	return ans;

// }

void before(int mid)//预处理所有状态

{

	for(int i=0;i<(1<<mid);i++)

	{

		if(check(i))

		{

			str[++cnt]=i;

			// sum[cnt]=getSum(i);

		}

	}

}

int main()

{

	int n,m;

	cin >> n >> m;

	int a;

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

	{

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

		{

			scanf("%d", &a);

			if(a==0) map[i]|=(1<<(j-1));//运用|运算的性质来构造反码

		}

	}

	before(m);//预处理

	// cout << "cnt = " << cnt << endl;

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

	{

		if(!(str[i] & map[1]))

		{

			dp[1][i]=1;

		}

	}

	// for(int i=1;i<=n;i++) printf("%d ",map[i]);

	// puts("");

	// for(int i=1;i<=cnt;i++) printf("%d ",dp[1][i]);

	// puts("");

	for(int i=2;i<=n;i++)//转移

	{

		for(int j=1;j<=cnt;j++)//枚举i的状态

		{

			if(str[j] & map[i]) continue;//判断状态是否合法

			for(int k=1;k<=cnt;k++)//枚举i-1的状态

			{

				if(str[k] & map[i-1]) continue;

				if(str[j] & str[k]) continue;

				dp[i][j]+=dp[i-1][k];

			}

		}

	}

	int ans=0;

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

	{

		if(map[n]&str[i]) continue;

		ans+=dp[n][i];

		ans%=mod;//重要，不加luogu会WA 10%

	}

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

	return 0;

}

　　　　小结：第2道状压。调试时候不要忘记题目所求的，在发现一个题与另一个题相似时不要被另一道题所局限

巴特西

[poj3254]Corn Fields_状压dp

最新文章

热门文章