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