[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));
	}
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology