| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
32ms,比较弱的代妈,用了STL的#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> trans[12][2048];
bool jsed[12] = {0};
bool has(int n, int b){
return (n & (1<<b)) > 0;
}
int J[13] = {0};
int getJ(int ip){
if(J[ip] > 0) return J[ip];
int ans = (1<<ip) + (1<<(ip+1));
J[ip] = ans;
return ans;
}
void js(int h){
jsed[h] = 1;
int p2 = (1 << h);
for(int i = 0; i < p2; i++){
vector<int> pos;
for(int j = 0; j < h-1; j++){
if(!has(i, j) && !has(i, j+1)) pos.push_back(j);
}
int sz = pos.size();
trans[h][i].push_back(p2-1-i);
for(int i1 = 0; i1 < sz; i1++){
trans[h][i].push_back(p2-1-i-getJ(pos[i1]));
}
for(int i1 = 0; i1 < sz-1; i1++){
for(int i2 = i1+1; i2 < sz; i2++){
if(pos[i2]-pos[i1]<=1) continue;
trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2]));
}
}
for(int i1 = 0; i1 < sz-2; i1++){
for(int i2 = i1+1; i2 < sz-1; i2++){
if(pos[i2]-pos[i1]<=1) continue;
for(int i3 = i2+1; i3 < sz; i3++){
if(pos[i3]-pos[i2]<=1) continue;
trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2])-getJ(pos[i3]));
}
}
}
for(int i1 = 0; i1 < sz-3; i1++){
for(int i2 = i1+1; i2 < sz-2; i2++){
if(pos[i2]-pos[i1]<=1) continue;
for(int i3 = i2+1; i3 < sz-1; i3++){
if(pos[i3]-pos[i2]<=1) continue;
for(int i4 = i3+1; i4 < sz; i4++){
if(pos[i4]-pos[i3]<=1) continue;
trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2])-getJ(pos[i3])-getJ(pos[i4]));
}
}
}
}
for(int i1 = 0; i1 < sz-4; i1++){
for(int i2 = i1+1; i2 < sz-3; i2++){
if(pos[i2]-pos[i1]<=1) continue;
for(int i3 = i2+1; i3 < sz-2; i3++){
if(pos[i3]-pos[i2]<=1) continue;
for(int i4 = i3+1; i4 < sz-1; i4++){
if(pos[i4]-pos[i3]<=1) continue;
for(int i5 = i4+1; i5 < sz; i5++){
if(pos[i5]-pos[i4]<=1) continue;
trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2])-getJ(pos[i3])-getJ(pos[i4])-getJ(pos[i5]));
}
}
}
}
}
}
}
int main() {
while(1){
int w, h;
scanf("%d%d", &w, &h);
if(w == 0 && h == 0) break;
if((w*h)%2 == 1){
printf("0\n");
continue;
}
if((!(jsed[w] ^ jsed[h]) && w < h) || (jsed[w] && (!jsed[h]))){
int temp = h;
h = w;
w = temp;
}
if(h == 1){
printf("1\n");
continue;
}
if(!jsed[h]){
js(h);
}
long long int dp[12][2048] = {0};
int p2 = (1<<h);
//初始值:要么洞要么棍
for(int i = 0; i < p2; i++){
bool ok = 1;
bool st[12];
for(int j = 0; j < h; j++){
if((i & (1<<j)) > 0) st[j] = 1;
else st[j] = 0;
}
int cnt = 0;
for(int j = 0; j < h; j++){
if(st[j]){
if(cnt%2 != 0){
ok = 0;
break;
}
cnt = 0;
}
else{
cnt++;
}
}
if(cnt%2 != 0) ok = 0;
if(ok) dp[1][i] = 1;
else dp[1][i] = 0;
}
//for(int i = 0; i < p2; i++) cout << dp[1][i] << " "; cout << endl;
for(int i = 2; i <= w; i++){
if(i == w){
int sz = trans[h][0].size();
long long int temp = 0;
for(int j = 0; j < sz; j++){
temp += dp[i-1][trans[h][0][j]];
}
//cout << temp;
printf("%I64d\n", temp);
break;
}
for(int j = 0; j < p2; j++){
long long int temp = 0;
int sz = trans[h][j].size();
for(int k = 0; k < sz; k++){
temp += dp[i-1][trans[h][j][k]];
}
dp[i][j] = temp;
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator