poj 1185 炮兵阵地（状态压缩dp）

题目链接

如果你是刚刚开始做状态压缩dp，我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单，更容易入门的题目。还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数具体请看我博客中 x& (x - 1)==0 这篇文章链接。还有一点，不同于poj 3254的地方，我们不能直接枚举所有的状态。我在getresult()中用到了四重循环，直接枚举的时间复杂度是2^40，并且dp那个数组也是开不下到，不过对于这道题还是有方法的。枚举一行所有的状态，行合法（没有两个1相隔少于两个）的状态总共有61中，我们只需要枚举所有合法状态即可，循环次数最多是61^4。

代码

代码语言：javascript复制

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 62;          //每行合法的状态总共有61种
int dp[102][maxn][maxn];      //因为状态是与前两行有关，所以用到三维数组
int sta[102];                 //每行不能放置的点
int cnt[maxn];                //状态中1的数目，也就是炮的数目
int allsta[maxn];             //所有可能的状态
int n, m;
int num;                      //满足条件的状态数

bool judgeself(int x)         //判断x状态是不是有会相互攻击的状态，也就是有没有两个1相隔少于两个0
{
    if (x&(x<<1) || x&(x<<2))
        return false;
    return true;
}

int count(int x)              //用很巧妙的计算出x二进制中1的个数
{
    int s = 0;
    while (x)
    {
        s  ;
        x = x&(x-1);
    }
    return s;
}

void search(int x)
{                                   //这个函数相当于把对状态进行了离散化，去掉了每行所有不合法的状态
    int t = 1<<x;
    num = 0;
    for (int i = 0; i < t; i  )
    {
        if (judgeself(i))
        {
            allsta[num] = i;
            cnt[num] = count(i);
            num  ;
        }
    }
}

bool fit(int x, int y)
{
    if(x&y)
        return false;
    return true;
}

void getresult()
{
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < num; i  )              //因为计算每行的时候需要用到前两行的状态，需要对第一行特殊处理
    {
        for (int j = 0; j < num; j  )
        {
            if (fit(sta[1], allsta[i]) && fit(allsta[i], allsta[j]))
                dp[1][j][i] = cnt[i];
        }
    }
    for (int i = 2; i <= n; i  )
    {
        for (int j = 0; j < num; j  )
        {
            if (!fit(sta[i], allsta[j]))
                continue;
            for (int k = 0; k < num; k  )
            {
                if (!fit(allsta[j], allsta[k]))           // 判断是否与前一行冲突
                    continue;
                for (int l = 0; l < num; l  )
                {
                    if (!fit(allsta[j], allsta[l]))       //不光要判断是否与前一行冲突，要判断第前两行
                        continue;
                    dp[i][k][j] = max(dp[i][k][j], dp[i-1][l][k] cnt[j]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < num; i  )
    {
        for (int j = 0; j < num; j  )
        {
            if (!fit(allsta[i], allsta[j]))
                continue;
            ans = max(ans, dp[n][i][j]);              //求出最后一行最大的结果
        }
    }
    printf("%dn", ans);
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        memset(sta, 0, sizeof(sta));
        search(m);
        for (int i = 1; i <= n; i  )
        {
            getchar();
            for (int j = 1; j <= m; j  )
            {
                char t;
                scanf("%c", &t);
                if (t == 'H')
                    sta[i]  = (1<<(m-j));            //标记一行中不能安放炮兵的状态
            }
        }
        getresult();
    }
    return 0;
}

dp 博客二进制入门

0 人点赞

poj 1185 炮兵阵地 （状态压缩dp）

poj 1185 炮兵阵地（状态压缩dp）