hdu4539(状态压缩)

题目链接：hdu4539

曼哈顿距离――两点在南北方向上的距离加上在东西方向上的距离，即d（i，j）=|xi-xj|+|yi-yj|。

本题每个士兵曼哈顿距离为2的位置不能有其他的士兵，假设士兵位置（i，j），则（i-2，j）（i+2，j）（i，j-2）（i，j+2）（i-1，j-1）（i-1，j+1）（i+1，j-1）（i+1，j+1）这些位置都不能有其他的士兵。

思路：状态压缩，相邻三行产生关系可以通过添加状态的维数来解

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int sta[200]; int map[200][15]; int d[105][200][200];//d[i][j][k]表示第i行第j个状态，第i-1行第k个状态下的最大士兵数 int n,m; int Init(int n)//预处理状态 { int M = 0; for(int i = 0; i < n; i ++) if( (i&(i>>2)) == 0 && (i&(i<<2)) == 0 ) sta[M++] = i; return M; } int Getsum(int i, int x) { int sum = 0, j = m - 1; while(x) { if(x&1) sum += map[i][j]; x >>= 1; j --; } return sum; } int main() { int i,j,k; while(~scanf("%d%d",&n,&m)) { int M = Init(1<
      
       >1)) || (sta[j]&(sta[k]<<1))) continue;//第i行和第i-1行冲突 if(i == 0) { d[i][j][k] = Getsum(i, sta[j]); ans = max(ans, d[i][j][k]); continue; } int tmp = 0; for(int p = 0; p < M; p ++)//第i-2行状态 { if((sta[p]&(sta[k]>>1)) || (sta[p]&(sta[k]<<1))) continue;//第i-1行和第i-2行冲突 if(sta[j]&sta[p]) continue;//第i行和第i-2行冲突 tmp = max(tmp, d[i-1][k][p]); } d[i][j][k] = tmp + Getsum(i, sta[j]); ans = max(ans, d[i][j][k]); } } } printf("%d\n",ans); } return 0; }