wenbao与轮廓线dp

-----------------------------------------------------------------------

入门题经典

http://poj.org/problem?id=2411

1*2地板铺地

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 const int maxn = 15;
 7 long long d[2][1<<maxn], f[15][15];
 8 int sum = 0, n, m;
 9 
10 void update(int x, int y){
11     if(y&(1<<m)) d[sum][y^(1<<m)] += d[1-sum][x];
12 }
13 
14 void solve(){
15     sum = 0;
16     memset(d, 0, sizeof(d));
17     d[0][(1<<m)-1] = 1;
18     for(int i = 0; i < n; ++i){
19         for(int j = 0; j < m; ++j){
20             sum ^= 1; //利用二维数组保存现在的状态与上一个状态
21             memset(d[sum], 0, sizeof(d[sum]));
22             for(int k = 0; k < (1<<m); ++k){
23                 update(k, k<<1); //不放        1<<(m-1)为1
24                 if(i && !(k&(1<<(m-1)))) update(k, (k<<1)^(1<<m)^1); //竖放        i != 0 && 1<<(m-1)不为1 
25                 if(j && !(k&1)) update(k, (k<<1)^3); //横放        j != 0 && 1<<0 为0 && 1<<(m-1) 为1
26             }
27         }
28     }
29     f[m][n] = d[sum][(1<<m)-1];
30 }
31 
32 int main(){
33     while(~scanf("%d%d", &n, &m)){
34         if(n == 0 && m == 0) break;
35         if(n < m) swap(n, m);
36         if(f[m][n]){
37             printf("%lld
", f[m][n]);
38         }else{
39             solve();
40             printf("%lld
", f[m][n]);
41         }
42     }
43     return 0;
44 }

-------------------------------------------------------

--------------------------------------------------------

只有不断学才能进步！