牧场的安排

https://loj.ac/problem/10171

题目描述

  牧场是一个(N*M)的矩阵，将在牧场里种草，有一些土地不能种植，并且种植满足不存在两块相邻的草地，求方案数。

思路

  比较显然我们可以将一行看做一个二进制数来考虑，那么就容易想到状压(dp)，我们直接预处理处满足这一行无相邻的符合条件的数(不考虑是否贫瘠)，接下来我们用(f[i][S])表示第(i)行状态为(S)的方案数，显然这个(S)要满足第(i)行能种下这块地，这一点我们可以通过二进制操作实现。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e8;

int p[550],a[20];
int f[14][550];
bool check(int x,int m)
{
	if(x==0)return 1;
	else return (~a[x])&p[m];
}
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		int s=0;
		for(int j=1;j<=n;j++)
		{
			int x;
			scanf("%d",&x);
			s=s*2+x;
		}
		a[i]=s;
	}
	int cnt=0;
	for(int i=0;i<(1<<n);i++)
	{
		if(i&(i<<1))continue ;
		p[++cnt]=i;
	}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=cnt;j++)
		{
			if(check(i,j))continue ;
			if(i==1){f[i][j]=1;continue ;}
			for(int k=1;k<=cnt;k++)
			{
				if(check(i-1,k))continue ;
				if(!(p[j]&p[k]))
					f[i][j]=(f[i][j]+f[i-1][k])%mod;
			}
		}
	int ans=0;
	for(int i=1;i<=cnt;i++)
		ans=(ans+f[m][i])%mod;
	printf("%d
",ans);
}