[TIOJ] 1452. 巧拼放置問題 (插頭DP/輪廓線DP)

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

---

就我所知，本題有兩種寫法，一種做法應該是被稱為「插頭DP/輪廓線DP」，想法不難，就是紀錄$dp[i][j][S]$為前$i-1$排都填滿了，且第$i$排由左往右$j$個也填滿了，而S則是記錄哪邊有凸出來(因為填滿也可以用直的填)，然後我這裡是往後轉移，轉移的方式也還算容易，就看他下一格是不是已經被填了(在S裡看)，如果沒被填就表示可以一個往下指的直的，且如果下兩格也沒被填就也可以擺一個橫的。最後看$dp[n-1][m-1][0]$即可。不過這題因為空間有點卡，所以要滾動一下。

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

const int N = 15;

lld dp[2][N][(1<<N)+5];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	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][0], dp[0][m-1]+(1<<m), 0);
		dp[0][1][0]=1;
		dp[0][0][1]=1;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(j==m-1) fill(dp[(i+1)&1][0], dp[(i+1)&1][m-1]+(1<<m), 0);
				for(int s=0;s<(1<<m);s++){
					if(j==m-1){
						if(s & 1) dp[(i+1)&1][0][s-1]+=dp[i&1][j][s];
						else{
							dp[(i+1)&1][0][s + 1]+=dp[i&1][j][s];
							if( !(s & 2) )
								dp[(i+1)&1][1][s]+=dp[i&1][j][s];
						}
					}else{
						if(s & (1<<(j+1))){
							dp[i&1][j+1][s - (1<<(j+1))]+=dp[i&1][j][s];
						}else{
							dp[i&1][j+1][s + (1<<(j+1))]+=dp[i&1][j][s];
							if( !(s & (1<<(j+2))) )
								dp[i&1][j+2][s]+=dp[i&1][j][s];
						}
					}
				}
			}
		}
		cout<<dp[(n-1)&1][m-1][0]<<'\n';
	}
	return 0;
}