【luogu P1879】【jzoj 7199】Corn Fields G / 又是他Farmer John / 玉米田（加強版）（狀壓DP）（輪廓線DP）

Corn Fields G / 又是他Farmer John / 玉米田（加強版）

題目連結：luogu P1879 / jzoj 7199

題目大意

給你一個 n*m 的矩陣，有一些位置可以選放不放東西。

然後規定一個東西旁邊四個位置不能有東西。

問你有多少種放的方案。

思路

看到這個大小，我們考慮狀壓 DP。

不難列出 2 n + m 2^{n+m} 2n+m 的式子，然後就能過 luogu 的。

但是 jzoj 的是加強版，就會 TLE。

我們考慮優化，寫輪廓線 DP。

輪廓線 DP 大概就是你設 f i , j , k f_{i,j,k} fi,j,k​ 就是處理到 i , j i,j i,j 的位置，輪廓線狀态是 k k k 的方案數。

處理到時什麼意思呢？

這個就是處理到 3 , 2 3,2 3,2， 就相當于假設你要看 4 , 2 4,2 4,2 的位置，那能影響它的就 3 , 2 3,2 3,2 跟 4 , 1 4,1 4,1。（後面的我們先不管）那我們就隻需要關心每列最小面的值，狀态個數就由 2 n + m 2^{n+m} 2n+m 變成 2 n / 2 m 2^n/2^m 2n/2m。

（雖然在這道題中我是豎着來的，不過是同一個道理）

然後就轉移，先看你原來狀态的要看的位置，如果有 1 1 1 就隻能不選。

然後否則就是可以選可以不選，自己轉移一下就可以了。

（不會轉移？自己看代碼去）

然後複雜度啊就是 O ( n m 2 m ) O(nm2^{m}) O(nm2m) 加點 O2 就可以過掉 jzoj。

代碼

#pragma GCC optimize(2)

#include<cstdio>
#include<cstring>
#define mo 100000000

using namespace std;

bool a[21][21];
int n, m, now, re;
int f[2][530001], ans;
char c;

int read() {
	re = 0;
	c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0'; 
		c = getchar();
	}
	return re;
}

int main() {
//	freopen("cowfood.in", "r", stdin);
//	freopen("cowfood.out", "w", stdout);
	
	n = read(); m = read();
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++)
			a[i][j] = read();
	
	f[0][0] = 1; now = 0; 
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++) {
			now ^= 1;
			for (int k = 0; k < (1 << m); k++) f[now][k] = 0;
			for (int k = 0; k < (1 << m); k++) {
				int up = (1 << j) & k, lft = (j == 0 ? 0 : (1 << (j - 1)) & k);
				if (i == 1 && up) continue;//出現非法情況
				if (j == 0 && lft) continue;
				if (up) {//隻能不選
					f[now][k ^ (1 << j)] += f[now ^ 1][k];
					if (f[now][k ^ (1 << j)] > mo) f[now][k ^ (1 << j)] -= mo;
					continue;//注意這裡原本是選的，要變成不選，是以要疑惑
				}
				if (lft || !a[i][j]) {//這裡也是隻能不選，但原本就是不選
					f[now][k] += f[now ^ 1][k];
					if (f[now][k] > mo) f[now][k] -= mo;
					continue;
				}
				//可以選也可以不選
				f[now][k] += f[now ^ 1][k];
				if (f[now][k] > mo) f[now][k] -= mo;
				f[now][k ^ (1 << j)] += f[now ^ 1][k];
				if (f[now][k ^ (1 << j)] > mo) f[now][k ^ (1 << j)] -= mo;
			}
		}
	
	for (int i = 0; i < (1 << m); i++)
		ans = (ans + f[now][i]) % mo;
	printf("%d", ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}