hdu 3502 bfs+状态压缩dp

?

题意是给你n*m的矩阵 每个单位有一个数，-1表示不能走 》=0表示有有多少个能量能获得 问从左上角到右下角能获得的做大能量值（走一步消耗1单位能量）

思路： 先bfs求出所有线之间的最短距离（当然 有用的只有有能量值的点和起点，终点） 然后状态压缩dp 找到最大能量值 这里有几个注意的地方

状态尽量从1开始 减少数组的空间（爆了一次） 其次是bfs是只搜有能量的点 其它都差不多；

?

?

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; #define INF 0x3f3f3f3f 
       int map
      [300
      ][300
      ],dis
      [25
      ][25
      ],mark
      [300
      ][300
      ],leap
      [300
      ][300
      ]; int dir
      [4
      ][2
      ]={0
      ,1
      ,0
      ,-1
      ,1
      ,0
      ,-1
      ,0
      }; int coord
      [25
      ][3
      ],dp
      [1
      <<18
      ][20
      ],n
      ,m
      ; struct node
       { int x
      ,y
      ; int step
      ; }a
      ,b
      ; int min
      (int a
      ,int b
      ) { return a
      <b
      ?a
      :b
      ; } int bfs
      (int k
      ) { int i
      ; a
      .x
      =coord
      [k
      ][1
      ]; a
      .y
      =coord
      [k
      ][2
      ]; a
      .step
      =0
      ; queue
      <node
      >q
      ; memset
      (mark
      ,0
      ,sizeof(mark
      )); mark
      [a
      .x
      ][a
      .y
      ]=1
      ; q
      .push
      (a
      ); while(!q
      .empty
      ()) { b
      =q
      .front
      (); q
      .pop
      (); for(i
      =0
      ;i
      <4
      ;i
      ++) { a
      .x
      =b
      .x
      +dir
      [i
      ][0
      ]; a
      .y
      =b
      .y
      +dir
      [i
      ][1
      ]; a
      .step
      =b
      .step
      +1
      ; if(a
      .x
      <=0
      ||a
      .x
      >n
      ||a
      .y
      <=0
      ||a
      .y
      >m
      ) continue; if(map
      [a
      .x
      ][a
      .y
      ]==-1
      ) continue; if(mark
      [a
      .x
      ][a
      .y
      ]==0
      ) { mark
      [a
      .x
      ][a
      .y
      ]=1
      ; dis
      [k
      ][leap
      [a
      .x
      ][a
      .y
      ]]=dis
      [leap
      [a
      .x
      ][a
      .y
      ]][k
      ]=a
      .step
      ; q
      .push
      (a
      ); } } } return 0
      ; } int max
      (int a
      ,int b
      ) { return a
      >b
      ?a
      :b
      ; } int main() { int i
      ,j
      ; while(~scanf
      ("%d%d"
      ,&n
      ,&m
      )) { for(i
      =1
      ;i
      <=n
      ;i
      ++) for(j
      =1
      ;j
      <=m
      ;j
      ++) { scanf
      ("%d"
      ,&map
      [i
      ][j
      ]); leap
      [i
      ][j
      ]=-1
      ; } if(map
      [1
      ][1
      ]==0
      &&(n
      >1
      ||m
      >1
      )) {printf
      ("you loss!\n"
      );continue;} else if(n
      ==1
      &&m
      ==1
      ) {printf
      ("%d\n"
      ,map
      [1
      ][1
      ]);continue;} int t
      =-1
      ; for(i
      =1
      ;i
      <=n
      ;i
      ++) for(j
      =1
      ;j
      <=m
      ;j
      ++) { if(map
      [i
      ][j
      ]>0
      ) { coord
      [++t
      ][1
      ]=i
      ; coord
      [t
      ][2
      ]=j
      ; leap
      [i
      ][j
      ]=t
      ; } } if(map
      [n
      ][m
      ]==0
      ) { coord
      [++t
      ][1
      ]=n
      ; coord
      [t
      ][2
      ]=m
      ; leap
      [n
      ][m
      ]=t
      ; } memset
      (dis
      ,INF
      ,sizeof(dis
      )); for(i
      =0
      ;i
      <t
      ;i
      ++) { dis
      [i
      ][i
      ]=0
      ; bfs
      (i
      ); } dis
      [t
      ][t
      ]=0
      ; memset
      (dp
      ,-1
      ,sizeof(dp
      )); dp
      [1
      ][0
      ]=map
      [1
      ][1
      ]; int k
      =(1
      <<(t
      +1
      )); int Max
      =-1
      ; for(i
      =1
      ;i
      <k
      ;i
      ++) { for(j
      =0
      ;j
      <=t
      ;j
      ++) { if((i
      &(1
      <<j
      ))==0
      ) continue; if(dp
      [i
      ][j
      ]<0
      ) continue;//开始少了这句超时了一次 for(int x
      =0
      ;x
      <=t
      ;x
      ++) { if(x
      ==j
      ) continue; if(dp
      [i
      ][j
      ]<dis
      [j
      ][x
      ]) continue; if((i
      &(1
      <<x
      ))!=0
      ) continue; dp
      [i
      |(1
      <<x
      )][x
      ]=max
      (dp
      [i
      |(1
      <<x
      )][x
      ],dp
      [i
      ][j
      ]-dis
      [x
      ][j
      ]+map
      [coord
      [x
      ][1
      ]][coord
      [x
      ][2
      ]]); Max
      =max
      (Max
      ,dp
      [i
      |(1
      <<x
      )][x
      ]-dis
      [x
      ][t
      ]); //printf("^^^ %d\n",Max); 
       } } } if(Max
      <0
      ) printf
      ("you loss!\n"
      ); else printf
      ("%d\n"
      ,Max
      ); } return 0
      ; }
     
    
   
  

?

?