POJ —— 3254 Corn Fields（状态压缩dp）

╰半夏微凉° 2021-09-26 12:32 276阅读 0赞

题目链接：[http://poj.org/problem?id=3254][http_poj.org_problem_id_3254]

题目：

Corn Fields

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;17942</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;9451</td> 
  </tr> 
 </tbody> 
</table>

Description

Farmer John has purchased a lush new rectangular pasture composed of *M* by *N* (1 ≤ *M* ≤ 12; 1 ≤ *N* ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: *M* and *N*   
Lines 2..*M*\+1: Line *i*\+1 describes row *i* of the pasture with *N* space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

2 3
    1 1 1
    0 1 0

Sample Output

Hint

Number the squares as follows:

1 2 3
      4

There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.

题目描述：

状态压缩动态规划题，算是入门题吧，状态压缩整体思想不难，说白了就是把多个状态进行压缩处理，比如可以用一个十进制整数x的二进制形态来表示多个状态，例如x=5，其二进制表示为101，如果用0,1来表示状态的值，那么x就可以表示三个状态的值，1,0,1，这个思想还是比较容易想到的，难在于结合了动态规划，在实现方式，状态的选取， 还有状态的转移等等，我也是刚开始接触这类题，嗯，又学习了一点新知识。

本题给出一个n\*m的01矩阵，1代表可以种植的土地，0代表不可种植的土地，另外，相邻的格子不能同时种植，问有多少种种植方案。dp\[i\]\[j\]表示第i行的j种状态下最多有多少种方案，状态转移方程：dp\[i\]\[j\] = dp\[i\]\[j\] + dp\[i - 1\]\[k\]。答案就是最后一行所有状态的方案数之和。

代码：

#include<stdio.h>
    #include<string.h>
    int q[600];
    int v[15];
    int dp[15][600];
    const int mod = 100000000;
    int main()
    {
    	int a,b,i,j,k;
    	while(scanf("%d%d",&a,&b)!=EOF){
    		for(i = 1;i <= a;i ++){
    			int w;
    			v[i] = 0;
    			for(j = 1;j <= b;j ++){
    				scanf("%d",&w);
    				if(!w)    //这里用0来表示肥沃的土地，1表示不可种植的土地，循环结束后样例v[1]的值为0（0），v[2]的值为5（101）。
    					v[i] += (1<<(b - j));
    			}
    		}
    		int top = 0;
    		for(i = 0;i < (1<<b);i++){        //这里筛选出所有可行的状态，相邻格子不能同时为1。这里的1表示种植的土地。
    			if((i&(i<<1))==0)
    				q[top++] = i;
    		}
    		memset(dp,0,sizeof(dp));
    		for(i = 0;i < top;i ++){        //初始化dp数组
    			if((q[i]&v[1]) == 0)    //如果当前的状态和数据不矛盾则记录dp[1][i] = 1.
    				dp[1][i] = 1;
    		}
    		for(i = 2;i <= a;i ++){
    			for(j = 0;j < top;j ++){
    				if((q[j]&v[i]) == 0){        //如果当前状态符合当前行数据则进入
    					for(k = 0;k < top;k ++){
    						if(((q[k]&v[i - 1]) == 0) && ((q[k]&q[j]) == 0)){    //如果q[k]状态和上一行i-1的数据不矛盾且和q[j]不矛盾则累加。
    							dp[i][j] = (dp[i][j] + dp[i - 1][k])%mod;
    						}
    					}
    				}
    			}
    		}
    		int max = 0;
    		for(i = 0;i < top;i ++){
    			max = (max + (dp[a][i]%mod))%mod;
    		}
    		printf("%d\n",max);
    	}
    	return 0;
    }

[http_poj.org_problem_id_3254]: http://poj.org/problem?id=3254