[TIOJ] 1452. 巧拼放置問題 (狀態壓縮DP)

題目連結:http://tioj.infor.org/problems/1452

---

前面有提到，本題有兩種做法，另一種作法算是比較普通的狀態壓縮DP，狀態變成$dp[i][s]$代表第i排整排排完且$s$裡面的東東是突的。轉移時變成類似暴搜的感覺，對每一個點試試看可不可以放，然後轉到$dp[i+1][s ^{\prime} ]$。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

const int N = 15;

int n, m;
lld dp[N][1<<N];
void dfs(int,int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	while(cin>>n>>m, n!=0 or m!=0){
		if((n*m)&1){
			cout<<"0\n";
			continue;
		}
		if(m > n) swap(n, m);
		fill(dp[0], dp[n]+(1<<m), 0);
		dp[0][0]=1;
		for(int i=0;i<=n;i++)
			for(int s=0;s<(1<<m);s++)
				dfs(i, s, 0, 0);
		cout<<dp[n][0]<<'\n';
	}
	return 0;
}

void dfs(int i, int s, int j, int sp){
	if(j>m) return;
	if(j==m){
		dp[i+1][sp] += dp[i][s];
		return;
	}
	if(s & (1<<j)) dfs(i, s, j+1, sp);
	else{
		if( !(s & (1<<(j+1))) ) dfs(i, s, j+2, sp);
		dfs(i, s, j+1, sp+(1<<j));
	}
}