RQNOJ 328 炮兵阵地：状压dp

题目链接：https://www.rqnoj.cn/problem/328

题意：

　　司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。

　　一个N*M的地图由N行M列组成(N≤100,M≤10)，地图的每一格可能是山地（用'H' 表示），也可能是平原（用'P'表示），如下图。

　　在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；

　　一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

　　如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

　　图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

　　现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内）。

　　问在整个地图区域内最多能够摆放多少我军的炮兵部队。

题解：

　　表示状态：

　　　　m<=10，所以对每一行进行压缩。

　　　　dp[i][state1][state2] = max num of cannons（炮兵数量）

　　　　i：该摆第i行

　　　　state1：上上一行的状态(i-2)

　　　　state2：上一行的状态(i-1)

　　找出答案：

　　　　max dp[n][state1][state2]

　　　　枚举state1,state2.

　　如何转移：

　　　　now: dp[i][state1][state2]

　　　　枚举第i行填的方案为nex。

　　　　如果nex符合第i行的地形，并且与state1,state2均没有交集，则：

　　　　dp[i+1][state2][nex] = max dp[i][state1][state2] + sum[nex]

　　　　（sum[nex]为方案nex中的炮兵个数。）

　　边界条件：

　　　　dp[0][0][0] = 0

　　　　others = -1

　　　　（第0行的上两行方案均设为0，因为不填适用于任何地形）

　　优化：

　　　　（1）预处理field数组。

　　　　　　field[i]为第i行的地形。每一位上1位山地，0为平原。

　　　　　　判断nex是否适用于第i行时，只需判断是否有 state & field == 0

　　　　（2）预处理在一行上的合法方案。

　　　　　　在每一行上，两个炮兵之间最少相距2格。利用此性质dfs然后存起来就好。

　　　　（3）dp数组的下标state不再直接表示01状态，而是换成s代表当前方案在dfs数组中的索引。

　　　　　　省空间啊。。。

　　　　（4）预处理出每一种行上合法方案的sum值，存起来。

　　　　　　预处理时，最好用lowbit直接找出1，而不用逐位枚举。

AC Code:

 // optimizations:

 // scheme: put == 1, blank == 0

 // field: mountain == 1, plain == 0

 // legal: scheme & field == 0

 // preprocess: legal scheme for rows

 //

 // state expression:

 // dp[i][state1][state2] = max num of cannons

 // i: considering ith row

 // state1: top row

 // state2: bottom row

 //

 // find the answer:

 // max dp[n][state1][state2]

 //

 // transferring:

 // now: dp[i][state1][state2]

 // if nex & field[i] == 0

 // dp[i+1][state2][nex] = max dp[i][state1][state2] + sum[nex]

 //

 // boundary:

 // dp[0][0][0] = 0

 // others = -1

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stack>

 #define MAX_N 105

 #define MAX_M 15

 #define MAX_S 65

 using namespace std;

 int n,m;

 int cnt;

 int ans;

 int sum[MAX_S];

 int field[MAX_N];

 int legal_state[MAX_S];

 int dp[MAX_N][MAX_S][MAX_S];

 void dfs(int col,int state)

 {

     if(col>=m)

     {

         legal_state[cnt++]=state;

         return;

     }

     dfs(col+,state);

     dfs(col+,state|(<<col));

 }

 int cal_sum(int state)

 {

     int lowbit=state&-state;

     int cnt=;

     while(lowbit)

     {

         cnt++;

         state^=lowbit;

         lowbit=state&-state;

     }

     return cnt;

 }

 void read()

 {

     memset(field,,sizeof(field));

     cin>>n>>m;

     char c;

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

     {

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

         {

             cin>>c;

             field[i]<<=;

             if(c=='H') field[i]|=;

         }

     }

 }

 void solve()

 {

     cnt=;

     dfs(,);

     for(int i=;i<cnt;i++)

     {

         sum[i]=cal_sum(legal_state[i]);

     }

     memset(dp,-,sizeof(dp));

     dp[][][]=;

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

     {

         for(int s1=;s1<cnt;s1++)

         {

             for(int s2=;s2<cnt;s2++)

             {

                 int state1=legal_state[s1];

                 int state2=legal_state[s2];

                 if(dp[i][s1][s2]!=- && !(state1&state2))

                 {

                     for(int s3=;s3<cnt;s3++)

                     {

                         int nex=legal_state[s3];

                         if(!(nex&field[i]) && !(nex&state1) && !(nex&state2))

                         {

                             dp[i+][s2][s3]=max(dp[i+][s2][s3],dp[i][s1][s2]+sum[s3]);

                         }

                     }

                 }

             }

         }

     }

     ans=;

     for(int s1=;s1<cnt;s1++)

     {

         for(int s2=;s2<cnt;s2++)

         {

             ans=max(ans,dp[n][s1][s2]);

         }

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

RQNOJ 328 炮兵阵地：状压dp

最新文章

热门文章