记录编号	405058	评测结果	AAAAAAAAAA
题目名称	[POJ2411] Mondriaan's Dream	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.088 s
提交时间	2017-05-15 15:49:26	内存使用	0.35 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <deque>
#include <queue>
#include <string>
using namespace std;
const int MAXN = 12;
int n, m;
long long dp[2][1<<MAXN];
int main(){
  //freopen("test_data.txt", "r", stdin);
  freopen("examfive.in", "r", stdin);
  freopen("examfive.out", "w", stdout);
  while(~scanf("%d %d", &n, &m) && n && m){
    if(n < m)swap(n, m);
    long long *cur = dp[0], *last = dp[1];
    cur[0] = 1;
    for(int i = n-1; ~i; i--){
      for(int j = m-1; ~j; j--){
        for(long long k = 0; k < 1ll<<m; k++){
          if((k>>j & 1))last[k] = cur[k & ~(1<<j)];
          else{
            long long cnt = 0;
            if(j+1 < m && !(k>>(j+1)&1))
              cnt += cur[k|1<<(j+1)];
            if(i+1 < n)cnt += cur[k|(1<<j)];
            last[k] = cnt;
          }
        }
        swap(cur, last);
      }
    }
    printf("%lld\n", cur[0]);
    memset(dp, 0, sizeof(dp));
  }
  return 0;
}