POJ 1185-炮兵阵地【状压DP】

àì夳堔傛蜴生んèń 2023-10-11 10:24 9阅读 0赞

Description

司令部的将军们打算在N\*M的网格地图上部署他们的炮兵部队。一个N\*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

![format_png][]

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。  
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

Input

第一行包含两个由空格分割开的正整数，分别表示N和M；  
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。

Output

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

思路：可以发现我们不仅要考虑当前行的状态，还要考虑前两行的状态，所以我们设状态dp\[i\]\[j\]\[k\]就表示第i行状态为j，第i-1

行状态为k时前i行的答案，单纯枚举状态肯定是不行的。所以我们要预处理一下，找出来那些满足' 任意两个炮塔无法相互攻击'

的状态，放入集合S，那么我们枚举状态i 就代表S\[i\] 这个状态，还要预处理一下当前行什么状态是有效的，即可以放置炮塔的，

然后我们转移就行了。

转移的话我们考虑需要满足什么条件？当前行满足，上一行满足，前两行也满足，并且任意两行都不能有交集

那么 dp\[i\]\[j\]\[k\] = max(dp\[i - 1\]\[k\]\[s\])  + num\[j\]

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e2 + 10;
    const int inf = 0x3f3f3f3f;
    int mp[maxn];
    int dp[maxn][maxn][maxn], S[maxn], num[maxn];
    bool vis[maxn][maxn];
    int tot = 0, n, m;
    
    void init()
    {
        for(int i = 0; i < (1 << m); ++i) //相隔距离不小于3
        {
            bool flag = true; int last = -3;
            for(int j = 0; j < m; ++j)
            {
                if(i & (1 << j))
                {
                    if(j - last < 3)
                    {
                        flag = false;
                        break;
                    }
                    last = j;
                }
            }
            if(flag) S[++tot] = i;
        }
        for(int i = 0; i <= n; ++i) //vis[i][j]判断第i行状态为S[j]时是否合法
        {
            for(int j = 1; j <= tot; ++j)
            {
                if(i == 0)
                {
                    vis[i][j] = true;
                    continue;
                }
                bool flag = true;
                for(int k = 0; k < m; ++k)
                {
                    if((S[j] & (1 << k)) && !(mp[i] & (1 << k)))
                    {
                        flag = false;
                        break;
                    }
                }
                vis[i][j] = flag;
            }
        }
        for(int i = 1; i <= tot; ++i) //统计状态S[i]二进制1的个数
        {
            int cnt = 0;
            for(int j = 0; j < m; ++j)
                if(S[i] & (1 << j))
                    ++cnt;
            num[i] = cnt;
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        char c;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                cin >> c;
                if(c == 'P')
                    mp[i] += (1 << (m - j));
            }
        }
        init();
        memset(dp, -0x3f, sizeof(dp));
        dp[0][0][0] = 0;
        int ans = 0;
        for(int i = 1; i <= tot; ++i) //特殊考虑第一行
        {
            if(vis[1][i])
                dp[1][i][1] = num[i], ans = max(ans, num[i]);
        }
        for(int i = 2; i <= n; ++i)
        {
            for(int s = 1; s <= tot; ++s) //当前行
            {
                if(vis[i][s])
                {
                    for(int j = 1; j <= tot; ++j) //上一行
                    {
                        if(!(S[s] & S[j]) && vis[i - 1][j])
                        {
                            for(int k = 1; k <= tot; ++k) //上两行
                            {
                                if(!(S[s] & S[k]) && !(S[k] & S[j]) && vis[i - 2][k])
                                    dp[i][s][j] = max(dp[i][s][j], dp[i - 1][j][k]);
                            }
                            dp[i][s][j] += num[s];
                            if(i == n) //目标状态
                                ans = max(ans, dp[i][s][j]);
                        }
                    }
                }
            }
        }
        printf("%d\n", ans);
        return 0;
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3Bvai5vcmcvaW1hZ2VzLzExODVfMS5qcGc?x-oss-process=image/format,png