POJ 2411 Mondriaan's Dream

[DP]
JzDP

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#define LL long long int
using namespace std;
bool checkeven1(int a){
int c = 0;
while(a){
if(a&1)
c = 1-c;
else
if(c) return false;
a>>=1;
}
if(c) return false;
return true;
}
int main()
{
int h, w;
while(scanf("%d %d", &h, &w) == 2){
if((h == 0) and (w == 0)) break;
LL dp[13][1<<12];
for(int lx = 0;lx < (1<<w);lx++)
dp[0][lx] = (LL)checkeven1(lx);
for(int lh = 1;lh <= h;lh++){
for(int lx = 0;lx < (1<<w);lx++){
dp[lh][lx] = 0;
for(int ly = 0;ly < (1<<w);ly++)
if((lx|ly) == (1<<w)-1 and checkeven1(lx&ly))
dp[lh][lx] += dp[lh-1][ly];
}
}
printf("%lld\n", dp[h][0]);
}
return 0;
}