Hdu 4539 【状态DP】.cpp

题意：

　　一个炮兵可以攻打和他之间曼哈顿距离为2的士兵，给出你一块n*m的战场，告诉你哪些地方可以站人哪些地方不可以，问你最多可以安放多少个士兵?

　　n <= 100, m <= 10

思路：

　　这道题暴力是不可以的，因为状态太多了

　　可以状态DP来做，用一个数组G记录战场的限制，然后用一个数组dp[当前状态或者是前一个状态][当前状态的十进制表示][前一个状态的十进制表示]

　　因为用的是G[1<<m]来表示，所以时间复杂度是n*(2^m)*(2^m)*(2^m)，m最多为10，所以时间复杂度就是10*1024*1024*1024，显然这样的时间复杂度也是说不过去的。所以就用一个预处理，预处理出满足基本条件的状态，即水平距离上曼哈顿距离不为2的状态，我用bir[][2]来存预处理出来的基本状态，bir[][0]表示的是预处理的符合基本条件状态的二进制数，bir[][1]表示的是这个状态中1的个数

Tips：

　　因为用的是滚动数组，所以应该注意n == 1的情况

　　位运算的优先级比 != 高，所以当我判断是否符合条件的时候应该直接写if(***)或者是if((***) != 0)

　　不能写 == 1，因为不管是哪种位运算，出来的结果都不一定是1，只能是 != 0

　　这里还有一个处理状态sta里面有多少个1的有效办法就是用lowbit(x) { return (x)&(-x)}, lowbit(x)可以提取x的最后一个1至最后一个0，这个可以利用补码原理来理解

　　这样不断 i -= lowbit(i), bir[][1]++, 就可以得到相对应1的个数了

Code:

 #include <stdio.h>

 #include <cstring>

 #include <bitset>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int n, m;

 int G[], bir[<<|][], top;

 int dp[][<<|][<<|];

 int ans;

 int lowbit(int x)

 {

     return (x)&(-x);

 }

 void init()

 {

     top = ;

     int st = <<;

     for (int i = ; i < st; ++i) {

         if (((i>>)&i) || ((i<<)&i)) continue;

         int tmp = i;

         bir[top][] = i;

         while (tmp) {

             tmp -= lowbit(tmp);

             bir[top][]++;

         }

         top++;

     }

 }

 void DP()

 {

     int st = <<m;

     for (int i = ; i < top && bir[i][] < st; ++i)

         if ((bir[i][]&(G[]^(st-))) != ) continue; /// == 1!!!!!

         else ans = max(ans, bir[i][]);

     if (n == ) return;

     for (int i = ; i < top && bir[i][] < st; ++i) {

         for (int j = ; j < top && bir[j][] < st; ++j) {

             if (  (bir[i][]&(G[]^(st-))) !=

                 ||(bir[j][]&(G[]^(st-))) !=

                 ||((bir[i][]<<)&bir[j][]) || ((bir[i][]>>)&bir[j][])) continue;

             dp[][j][i] = bir[i][]+bir[j][];

             ans = max(ans, dp[][j][i]);

         }

     }

 // printf("___2___%d\n", ans);

     int t = ;

     for (int i = ; i < n; ++i) {

         for (int j = ; j < top && bir[j][] < st; ++j) {

             if (bir[j][]&(G[i-]^(st-))) continue;

             for (int k = ; k < top && bir[k][] < st; ++k) {

                 if (bir[k][]&(G[i-]^(st-))) continue;

                 for (int l = ; l < top && bir[l][] < st; ++l) {

                     if (  ((G[i]^(st-))&bir[l][])

                         ||(bir[l][]&bir[j][])

                         ||((bir[l][]<<)&bir[k][])

                         ||((bir[l][]>>)&bir[k][])) continue;

                     dp[t][l][k] = max(dp[t][l][k], dp[(t+)%][k][j]+bir[l][]);

                     ans = max(ans, dp[t][l][k]);

                 }

             }

         }

         t = (t+)%;

     }

 }

 int main()

 {

    // freopen("in.txt", "r", stdin);

     init();

     while (~scanf("%d %d", &n, &m)) {

         ans = -;

         memset(dp, , sizeof(dp));

         for (int i = ; i < n; ++i) {

             int p = , tmp;

             for (int j = ; j < m; ++j) {

                 scanf("%d", &tmp);

                 if(tmp != ) p |= (<<j); ///!!!!

             }

             G[i] = p;

         }

         DP();

         printf("%d\n", ans);

     }

     return ;

 }

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4539

巴特西

Hdu 4539 【状态DP】.cpp

最新文章

热门文章