DP课题6 POJ 1185 炮兵阵地

DP专题6 POJ 1185 炮兵阵地

传送门：http://poj.org/problem?id=1185

非常经典的DP问题，考虑了状态压缩，位运算，有的大牛还用了滚动数组。

这次不罗嗦，直接分析思路：

首先看复杂度，对于每一行，朴素的想法是放的可能性是2^n，n代表列数，但是题目要求在范围2以内不准再部署炮兵。所以，我们search每一行可能的情况，利用位运算。然后DP，对于每一行，具有无后效性：即这一行的部署情况只与本身以及前两行的情况有关。依次DP下去即可求解。关于状态压缩：比如1表示放置，1001为在4列的情况下一种部署，这个二进制数对应的十进制数为9，因此9可以唯一确定的代表这种情况。关于位运算：比如第一行1001 与第二行0110 ，两个二进制数&的结果为0表示可以按照这样部署，而1001 & 1000 = 8 != 0 ，所以不能这样部署，因为第一行的第一列和第二行的第一列都是放置了炮兵的，故舍弃。关于运用位运算，这是我第二次碰见，第一次碰见应该是在博弈论中的取石子问题。这些都是很巧妙的想法，C语言或者说ACM正是因为有这些巧妙的地方，让我们的思路更加开阔，让程序也有可爱的地方吧。

代码如下，这个题目第一次碰到的时候感觉很难，所以写的注释比较多：

/*Memory: 34248 KB   Time: 313 MS  
Language: GCC   Result: Accepted  
 
This source is shared by hust_lcl
*/
#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
int dp[101][1044][1044];
int h[104];//以状态压缩的方式记录一行的H（1）和P（0）
int acc[100],top;
char map[104][13];//存放输入数据
int n, m;

void ready()
{
    int state = 0;
    int i, j;
    h[0] = h[1] = -1;
    for(j = 0; j < n; j++)
    {
        state = 0;//对每一行标记以前都要令state = 0
        for(i = 0; i < m; i++)
        {
            state = state << 1;
            //对每一列处理完以后，在处理下一列时要将上一列的0/1左移一个单位
            if(map[j][i] == 'P')
              ;
            //如果为P，仍为0，无需特别处理
            else
              state += 1;
            //如果为H，则标记为1，i++后左移一位即可
        }
        //在上述的for循环后，实现了压缩存储，
        //例如HPHH，经过处理后就变成了1011
        //处理过程为0→1→10→100→101→1010→1011
        //此时state = (1011)2  = (11)10
        h[j+2] = state;
    }//for循环用来将地图中H标记为1 P标记为0
    top = 0;
    for(j = 0; j < (1<<m); j++)
    //在这里1向左移动m,m为列的个数，实际上是1*2^m，代表2^m种可能
    {
        if(j & (j<<1))
          continue;
        //此为冲突种类一
        //比如j = 3 二进制0011，代表在第三列和第四列都放置炮兵
        //显然0011 & 0110 = 4 ！=0 是不可取的选择
        //此时continue 继续下一个++
        if(j & (j<<2))
          continue;
        //此为冲突种类二
        //比如j = 7 0111 ,代表在第2、3、4列放炮兵
        //但是0111 & 11100 != 0
        //所以继续被除掉 j++
        acc[top++] = j;
        //如果上述两个if都不满足的话，说明是可行的
        //即该种方案不存在在某一个1的附近2个单位内存在1
        //这种方案成立
    }//此处for循环是判断对于每个独立的一行，可行的放置数top
}
//需要注意的是，上述ready过程中的两个处理都是独立的
//第一个处理是标记H为1 P为0
//第二个标记是假设全部为PPPPP 判断这独立的一行的情况

int count(int x)
{
    int cons = 0;
    while(x)
    {
        if(x & 1)cons++;
        x >>= 1;
    }
    return cons;
}

int main()
{
    int i, aj,j, k, l, cons = 0;
    int i1,ai1,j1,aj1;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++)
      scanf("%s", map[i]);//按行输入数据
    ready();//初始化工作
    for(i = 0; i < n; i++)//按行处理
    {
        for(aj = 0; aj < top; aj++)//top是每一行的可能摆放种数
        {
            j = acc[aj];//acc[aj]代表第aj个可行方案，采用了压缩存储
            if(j & h[i+2])
              continue;
            //h[i+2]存储的是第i行的地图标记情况
            //如果j & h[i+2] != 0 说明j方案在H初放置了炮兵
            //由于这是不允许的，因此删除
            for(ai1 = 0; ai1 < top; ai1++)
            //进入此for循环说明j是满足该行地图分布的可能性
            //即行内不冲突
            //此时需要比较行间是否冲突
            {
                i1 = acc[ai1];
                if(i1 & j)continue;
                if(i1 & h[i+1])continue;
                //上述判断是否和相邻的一行冲突
                for(aj1 = 0; aj1 < top; aj1++)
                {
                    j1 = acc[aj1];
                    if(j1 & j)continue;
                    if(j1 & i1)continue;
                    if(j1 & h[i])continue;
                    //此处判断是否和相邻的第二行冲突
                    dp[i+1][j][i1] = max(dp[i+1][j][i1], dp[i][i1][j1]);
                    //dp的状态方程，
                }
                dp[i+1][j][i1] += count(j);
            }
        }
    }
    for(i = (1<<m)-1; i >= 0; i--)
    {
        for(j = (1<<m)-1; j >= 0; j--)
        {
            cons = max(cons,dp[n][i][j]);
            //取最大的方案数
        }
    }
    printf("%d\n", cons);

}

DP课题6 POJ 1185 炮兵阵地

相关推荐