main.cpp

poj2411 基本0ms的算法

#include <algorithm>
#include <list>
#include <vector>
#include <iostream>
#include <functional>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
using namespace std;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;
typedef vector<char> vc;
int h,w,*tn,*tp,num;
int fn[2048],fp[2048];
void full(int,int);
int main()
{
	while(cin >> h >> w, h && w);
		cout << fill(h,w) << endl;
	return 0;
}

int fill(int h,int w)
{
	fp[0]=1;
	for(int i=0;i<h+1;++i)	
	{
		if(i%2==0) {tn=fn;tp=fp;} else {tn=fp;tp=fn;}
		for(int j=0;j< i<<w;++j)
			full(j,0);
	}
	return tn[0];
}

void full(int s,int k)
{
	if(k==w) {
		tn[num]+=tp[s];
		return;
	}
	if(k==0) num=0;
	if(s & 1<<w-k-1) full(s, k+1);
	else {
		if(k<w-1 && s & 1<<w-k-2) full(s,k+2);
		num|=1<<w-k-1;
		full(s,k+1);
	}
}