Processing math: 0%
当前位置:首页 > 动态规划 > 状压DP > 正文
[玉米田]POJ3254CornFields
3852+

题目大意:有一块n行m列的地,John需要在标记为1的地上种玉米,而且种植的玉米不能相邻,请问有多少种种植方法?[SSOJ2153]

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

9

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.

解题思路

看到这种小数据,不难想到状态压缩。把一行看成一个状态,1表示对应位置中玉米,0表示不种。一行一行种玉米,那么f[i][j]表示第i行状态为j的方案数,最终结果就是最有一行所有状态方案数之和。

状态转移:当前状态是b,上一行状态是a,如果a和b合法——在一行内不能相邻,且0的位置不能种玉米,那么f[i][b] += f[i-1][a],也就在前面的基础上,在第i行种b状态的玉米。

位运算优化:左右不相邻,即j&(j<<1)以及j&(j>>1)只能为0;上下不相邻,即上下两个状态a&b必须是0;0的地方不能种玉米,原来的状态装成二进制后,取反即得到0变1、1变0,与状态&运算后,如果有1,说明0的位置中玉米了,不可行。(方法还有很多……)

预处理状态玉米数量(1的个数),代码14行,递推出所有状态1的个数,状态1的个数=状态少一个1的1的个数+1。

预处理所有可行状态,因为2^12*2^12复杂度太高了,但不难想到一行12列,最多放种6个玉米,预处理后,2^12至少降低到C(12,6)以下。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

[玉米田]POJ3254CornFields:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!