【题解】poj 3254 Corn Fields

题目描述

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的玉米，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种玉米。并且，奶牛们喜欢独占一块地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块玉米地有公共边。
John想知道，如果不考虑玉米地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入输出格式

输入格式：

第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式：

一个整数，即牧场分配总方案数除以100,000,000的余数。

思路

数据n,m<=12,基本确定是状压dp

预处理所有有效(合法)的牛分布状态

则对于一个合法的状态i,有i&(i<<1)==0

int x=1<<12, k=0;

for(re i=0; i<x; i++) if(!(i&(i<<1))) cow_state[k++]=i;

处理土地

为了方便,把土地取反,即用1表示肥沃,0表示贫瘠

for(re i=0;i<M;i++)

　　for(re j=0;j<N;j++)

    {

	    scanf("%d",&t);

	    corn_state[i]=(corn_state[i]<<1)|!t;

　　 }

dp

两行的牛状态相位与要为0
牛状态和土地(种植)状态相位与要为0 (牛只会在肥沃的土地上)

具体看代码

代码

#include<cmath>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MOD 100000000

#define re register int

using namespace std;

inline int read(){

	int x=0,w=1;

	char ch=getchar();

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

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

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

	return x*w;

}

int corn_state[13], cow_state[377], dp[13][377];

int main()

{

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

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

    int x=1<<12, k=0;

    for(re i=0; i<x; i++)	                     	  			//计算牛的有效状态

        if(!(i&(i<<1))) cow_state[k++]=i;             			//如果是有效状态

    cow_state[k]=x;

    int M,N,t;

    M=read(),N=read();

    for(re i=0;i<M;i++)

        for(re j=0;j<N;j++)

        {

            scanf("%d",&t);

            corn_state[i]=(corn_state[i]<<1)|!t;            	//玉米状态取反,0表肥沃

		}

    x=1<<N;

    for(re i=0;cow_state[i]<x;i++)	                			//第一行初始化

        if(!(corn_state[0]&cow_state[i])) dp[0][i]=1;

    for(re r=1;r<M;r++)

        for(re i=0;cow_state[i]<x;i++)	             			//枚举上一行有效状态

        {

            if(!(corn_state[r-1]&cow_state[i]))             	//上一行的状态符合上一行的玉米分布

                for(re j=0;cow_state[j]<x;j++)	    			//枚举本行有效状态

                {

                    if(!(corn_state[r]&cow_state[j]))       	//状态符合这本行的玉米分布

                        if(!(cow_state[i]&cow_state[j]))    	//这一行和上一行不冲突

                            dp[r][j]=(dp[r][j]+dp[r-1][i])%MOD;

        		}

		}

    int r=M-1;

    for(re i=1;cow_state[i]<x;i++)				     			//最后一行

        dp[r][0]=(dp[r][0]+dp[r][i])%MOD;

    printf("%d\n", dp[r][0]);

    return 0;

}

巴特西

【题解】poj 3254 Corn Fields

题目描述

输入输出格式

思路

预处理所有有效(合法)的牛分布状态

处理土地

dp

代码

最新文章

热门文章