POJ 1185炮兵阵地 (状压DP)

2016-08-10 来源: 卷珠帘 发布在  http://www.cnblogs.com/littlepear/p/5759287.html

题目链接 POJ 1185

今天艾教留了一大堆线段树,表示做不动了,就补补前面的题。QAQ

这个题,我第一次写还是像前面HDU 2167那样写,发现这次影响第 i 行的还用i-2行那样,那以前的方法就行不通了。

找出所有可行的状态,因为每一行最大只有10列,所以一行里最多有4个,那它可行的状态不多(网上大多数说法最多是60个)。用dp[x][i][j]来转移,x表示第x行,i表示第x行的状态,j表示第x-1行的状态。先初始化前两行。

 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 ;
 #define legal(a,b) (a&b)
 int base[maxn];
 int state[maxn];
 int solders[maxn];
 int dp[maxn][maxn][maxn];
 ];
 ;
 int main()
 {
     int n,m;
     scanf("%d %d",&n,&m);
     ;i<n;i++)
     {
         scanf("%s",s[i]);
         ;j<m;j++)
         {
             <<j); //记录山地
         }
     }
     ;
     ;i<(<<m);i++) //删除一行中相互攻击的点
     {
         )||legal(i,i<<)) continue;
         int k = i;
         while(k) //记录里面有多少个炮台
         {
             solders[num]+=(&k);
             k=k>>;
         }
         state[num++] = i;
     }
     ;i<num;i++) //初始化第0行
     {
         ])) continue;
         dp[][i][] = solders[i];
     }
     ;i<num;i++)    //初始化第1行,此为第二行
     {
         ])) continue;
         ;j<num;j++)          //枚举第一行
         {
             ])) continue;
             if(legal(state[i],state[j])) continue;
             dp[][i][j] = max(dp[][i][j],dp[][j][]+solders[i]);
         }
     }

     ;r<n;r++)   //开始从第二行枚举
     {
         ;i<num;i++) //枚举r行
         {
             if(legal(state[i],base[r])) continue;
             ;j<num;j++) //枚举r-1行
             {
                 ])) continue;
                 if(legal(state[j],state[i])) continue;
                 ;k<num;k++) //枚举第r-2行
                 {
                     ])) continue;
                     if(legal(state[k],state[i])) continue;
                     if(legal(state[k],state[j])) continue;
                     dp[r][i][j] = max(dp[r][i][j],dp[r-][j][k]+solders[i]);
                 }
             }
         }
     }
     ;
     ;i<num;i++)
     {
         ;j<num;j++)
             maxx = max(maxx,dp[n-][i][j]);
     }
     printf("%d\n",maxx);
     ;
 }

相关文章