poj1038

黑书138面的题目。。典型的状态压缩dp。
而且神奇的用了3进制。。
思路看黑书了。。
直接上code
  1 /*
  2   State:Accepted
  3   Time:2013.3.23  14:10
  4 */
  5 #include<iostream>
  6 #include<cstring>
  7 #include<cstdlib>
  8 #include<cstdio>
  9 #include<fstream>
 10 #include<algorithm>
 11 #define M0(a) memset(a ,0,sizeof(a))
 12 using namespace std;
 13 int T , n , m , k;
 14 int map[160][20], num[15] , f[2][60000] , bit[60000][15] , data ;
 15 int opt , now ,maxm , nowi;
 16 
 17 void work_bit(int x){
 18      int k;
 19      k = x;
 20      while (x){
 21         ++bit[k][0];
 22         bit[k][bit[k][0]] = x % 3;
 23         x /= 3;
 24      }
 25 }
 26 
 27 void predone(){
 28      num[1] = 1;
 29      for (int i = 2; i <= 12; ++i)
 30            num[i] = num[i - 1] * 3;
 31      for (int i = 1; i <= 60000; ++i) work_bit(i);
 32 }
 33 
 34 void init(){
 35      int x , y;
 36      M0(map);
 37      scanf("%d%d%d",&n ,&m, &k);   
 38      for (int i = 1; i <= k; ++i){
 39          scanf("%d%d", &x , &y);
 40          map[x][y] = 1;
 41      }
 42 }
 43 
 44 void updata(int sta ,int add , int pos){
 45      if (pos > m){
 46           f[now][sta]= max(f[now][sta] , data + add);    
 47           return;
 48      }
 49      
 50      if (map[nowi][pos]){
 51             updata(sta + 2*num[pos], add, pos + 1);       
 52             return;      
 53      }
 54      
 55      if (bit[opt][pos]==0){
 56          updata(sta, add , pos+1);
 57          if (pos < m)
 58             if (bit[opt][pos + 1] == 0 && map[nowi][pos+1] == 0) 
 59                           updata(sta+2*num[pos]+2*num[pos+1], add+1, pos+2);
 60          if (pos <= m-2)
 61                  if (bit[opt][pos + 1] != 2 && map[nowi][pos +1] == 0
 62                    &&bit[opt][pos + 2] != 2 && map[nowi][pos +2] == 0)
 63                       updata(sta+2*num[pos]+2*num[pos+1]+2*num[pos+2],add+1, pos+3);
 64      }            
 65      
 66      if (bit[opt][pos] == 1){
 67          updata(sta, add, pos+1);
 68          if (pos <= m-2){
 69                  if (bit[opt][pos + 1] != 2 && map[nowi][pos +1] == 0
 70                    &&bit[opt][pos + 2] != 2 && map[nowi][pos +2] == 0)
 71                           updata(sta+2*num[pos]+2*num[pos+1]+2*num[pos+2], add+1, pos+3);
 72          }            
 73      }
 74      
 75      if (bit[opt][pos]==2) updata(sta + num[pos], add, pos+1);
 76      
 77 }
 78 void solve(){    
 79      if (m == 1 || n == 1 || m * n < 6){
 80            printf("0\n");
 81            return;
 82      }     
 83      maxm = num[m+1];
 84      for (int i = 0; i <= maxm; ++i)
 85         f[1][i] = -0xffffff;
 86         
 87      int st = 0;
 88      for (int i = 1; i <= m; ++i){
 89         if (map[1][i] == 0) st += num[i];
 90         if (map[1][i] == 1) st += num[i]*2;    
 91      }
 92     
 93      f[1][st] = 0;
 94      
 95      for (int i = 1; i < n; ++i){        
 96         nowi = i + 1;
 97         now = (nowi & 1);
 98         for (int j = 0; j <= maxm; ++j)
 99             f[now][j] = -0xffffff;
100         for (opt = 0; opt < maxm; ++opt)
101              if (f[i&1][opt] >= 0){
102                  data = f[i & 1][opt];
103                  updata( 0 , 0 , 1 );             
104              }
105       // for (int j = 0;  j < maxm; ++j)
106         //   if (f[now][j]>=0) printf("f[%d][%d] = %d\n" , i + 1, j ,f[now][j]);
107      }
108     int ans = 0;
109     for (int i = 0; i < maxm; ++i)
110         ans = max(ans , f[n&1][i]);
111     printf("%d\n",ans);
112 }
113 
114 int main(){
115      freopen("poj1038.in","r",stdin); 
116      freopen("poj1038.out","w",stdout);
117      scanf("%d",&T);
118      predone();
119      while (T --){
120             init();
121             solve();
122      }
123 }