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

Corn Fields G / 玉米田++ / 玉米田（加加強版）

題目連結：luogu P1879 / jzoj 7200

題目大意

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

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

問你有多少種放的方案。

思路

首先不會加強版的自己先回去看看我的加強版，本文是在那個的基礎上繼續搞，是以不會講思路，而是講如何優化。

——>加強版做法<——

然後我們發現第一個問題是空間，會爆。

你直接一個 f f f 數組就爆了。

但你仔細想想會發現有一些狀态根本就是不合法的。

那你輪廓線隻會有一個斷點，那一個頂多就會有一個地方連起來。

那如果有多個地方連起來，就說明這個狀态就是不合法的。

你可以把合法的找出來重新編号，經我的測試（不一定準），最多不超過 13 13 13 萬。

你就搞定了空間。

然後你枚舉也隻用枚舉這些位置，然後你會發現你時間也可以了。

。。。

然後雖然大資料在本地跑要 2s，甚至會 5s，但它會自動給你開 O2，在 OJ 上還是能過的。

然後就好啦。

代碼

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

using namespace std;

bool a[121][21];
int n, m, now, re;
int f[2][130001], ans, tot, num;
int to[2097152], fr[130001], yes;
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();
	
	memset(to, -1, sizeof(to));//把有用的狀态找出來
	for (int i = 0; i < (1 << m); i++) {
		num = 0; yes = 2;
		for (int j = 0; j < m; j++)
			if ((i >> j) & 1) {
				num++;
				if (num == 2 && yes == 2) {
					yes = 1;
					num = 1;
				}
				else if (num == 2 && yes == 1) {
					yes = 0;
					break;
				}
			}
			else num = 0;
		if (yes) {
			to[i] = tot++;
			fr[tot - 1] = i;
		}
	}
	
	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 < tot; k++) f[now][k] = 0;
			for (int k = 0; k < tot; k++) {
				int up = (1 << j) & fr[k], lft = (j == 0 ? 0 : (1 << (j - 1)) & fr[k]);
				if (i == 1 && up) continue;
				if (j == 0 && lft) continue;
				if (up) {
					if (to[fr[k] ^ (1 << j)] == -1) continue;
					f[now][to[fr[k] ^ (1 << j)]] += f[now ^ 1][k];
					if (f[now][to[fr[k] ^ (1 << j)]] > mo) f[now][to[fr[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;
				if (to[fr[k] ^ (1 << j)] == -1) continue;
				f[now][to[fr[k] ^ (1 << j)]] += f[now ^ 1][k];
				if (f[now][to[fr[k] ^ (1 << j)]] > mo) f[now][to[fr[k] ^ (1 << j)]] -= mo;
			}
		}
	
	for (int i = 0; i < tot; i++)
		ans = (ans + f[now][i]) % mo;
	printf("%d", ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}