题目：Corn Fields

题目来源：POJ3254

分析

题目大意为：

  1. 给定一个12*12的矩形，每个格子为0或1，0为不能放东西，1可以

  2. 现在放东西进格子里，一个格子可以放的条件：

    • 这个格子可以放（值为1）
    • 相邻的四个格子没有放

  3. 求有几种放法

注意到没有后效性，可以用动归做

以每行为阶段，以每行的放的情况为状态，压缩为二进制（N<=12）

状态转移的约束为1），2）条件

解法

F[I,J]表示第I行，状态为J

这样转移方程为

1
F[I, J] = SIGMA{ F[I-1, K] }  (j and k=0)

当然每行的状态确定前要先检查是否符合条件1

优化

如果每行都去考虑与地图的契合性，会非常浪费时间

因为J包含了所有可能，K也是，这样比较J,K就会包含许多无用的状态，J不符的和K不符的

这样转移复杂度会达到O(2^2N)将近7000W

所以要进行优化，将每行的符合地图的状态预处理出来

详解

边界为

1
F[0,0] = 1;

细节

注意要模100000000

源程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Program Lwx;
Const md=100000000;
Var 	n, m:longint;
       	i, j, k, l, a, b, c:longint;
       	f, g:array[0..15, 0..5000] of longint;
       	p:array[0..15] of longint;

Procedure given(x:longint);
Var i:longint;
Begin
	for i :=1 to n do
	if p[i] and x = 0 then
	begin
		inc(f[i, 0]);
		f[i, f[i, 0]]:=x;
	end;
End;

Procedure find(x, y:longint);
Var a, b, c:longint;
Begin
	if x = m then 
	begin
		given(y);
		exit;
	end;
	if y and 1= 0 then find(x+1,y shl 1+1);
	find(x+1, y shl 1);
End;

Begin
	//assign(input, 'test.in');reset(input);
	readln(n, m);
	for i := 1 to n do
	begin
		k := 0;
		for j :=1 to m do
		begin
			read(a);
			k := k shl 1 + (a+1) mod 2;
		end;
		p[i] := k;
	end;
	fillchar(f, sizeof(f), 0);
	find(0, 0);
	f[0, 0] := 1;
	f[0, 1] := 0;
	g[0, 1] := 1;
	for i := 1 to n do
	for j := 1 to f[i, 0] do
	begin
		g[i, j] := 0;
		for k :=1 to f[i-1, 0] do
		if f[i, j] and f[i-1, k]=0 then g[i, j] := (g[i, j]+g[i-1, k]) mod md;
	end;
	L := 0;
	for i := 1 to f[n, 0] do L := (L+g[n, i]) mod md;
	write(L);
	//close(input);
End.