【ybt高效進階5-5-1】種植方案（狀壓DP）（輪廓線DP）

種植方案

題目連結：ybt高效進階5-5-1

題目大意

給你一個 n*m 的矩陣，有一些點不可以放東西，有些放不放都行。

然後問你有多少種放的方案，使得滿足不會有兩個東西相鄰。

思路

明顯的狀壓。

想了想發現一行一行搞複雜度有點危，可能要壓狀态。

然後不想壓狀态的我就寫了個輪廓線 DP，跑得飛快。

ヾ(✿ﾟ▽ﾟ)ノ好耶~

代碼

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

using namespace std;

int n, m, f[2][4100], now, nxt, ans;
bool a[12][12];

int main() {
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &a[i][j]);
	
	now = 0; nxt = 1;
	f[now][0] = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			for (int fr = 0; fr < (1 << m); fr++) {
				int to = fr;//不選
				if ((to >> j) & 1) to ^= (1 << j);
				f[nxt][to] += f[now][fr];
				if (f[nxt][to] >= mo) f[nxt][to] -= mo;
				
				to = fr;//選
				if ((to >> j) & 1) continue;
				if (!a[i][j]) continue;
				if ((to >> (j - 1)) & 1) continue;
				to |= (1 << j);
				f[nxt][to] += f[now][fr];
				if (f[nxt][to] >= mo) f[nxt][to] -= mo;
			}
			
			memset(f[now], 0, sizeof(f[now]));
			now = nxt;
			nxt = now ^ 1;
		}
	
	for (int i = 0; i < (1 << m); i++)
		ans = (ans + f[now][i]) % mo;
	printf("%d", ans);
	
	return 0;
}