历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 292. 炮兵阵地【线性状压DP+常规优化+转移优化】原题链接中等

作者：

一只野生彩色铅笔 , 2021-07-20 23:57:22 , 所有人可见 , 阅读 7313

97

16

最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

对比y总原来的代码部分，在无效的转移状态枚举上进一步进行了优化，能更快一点

题目描述

给定一个 $N \times M$ 矩阵，矩阵中标有 $H$ 字样的位置不能放置棋子，标有 $P$ 字样的位置可以放置棋子

棋子的 攻击方向 为 上、下、左、右 四个方向， 攻击距离 为 2个格子

现在在该棋盘上放置棋子，使得棋子之前 不能被互相攻击 到，能够放置棋子的 最大个数

分析

关于如何对状态进行 二进制压缩，在 玉米田【线性状压DP】 有详细提及

关于如何不同层不同合法状态判断，在 小国王【线性状压DP】 有详细提及

以上两点在本篇博客中不会再重复提及

观察到数据范围 $0 \lt N \le 100, 0 \lt M \le 10$

故我们可以把行作为动态规划的阶段，然后对于第 i 行的摆放状态进行 状态压缩

这就变成了一道标准的 线性状压DP

但是本题不同于 小国王 和 玉米田，这两题中棋子的 攻击距离 只有1

因此在这两题里，我们只需压缩存储 当前层的状态 ，然后枚举 合法的上个阶段 的状态进行转移即可

但是本题的棋子攻击范围是 $2$，我们只压缩当前层一层状态后进行转移，是不能保证该次转移是 合法的

即不能排除第 $i-2$ 层摆放的棋子可以攻击到第 $i$ 层棋子的 不合法 情况

而解决该问题的手段就是：压缩存储两层的信息，然后枚举合法的第 $i-2$ 层状态进行转移即可

闫氏DP分析法

状态表示—集合$f_{i,j,k}:$ 考虑前 $i$ 层，且第 $i$ 层状态是 $j$，第 $i-1$ 层状态是 $k$ 的方案
状态表示—属性$f_{i,j,k}:$ 该方案能够放置棋子的最大个数 $Sum$
状态计算—$f_{i,j,k}:$
$$ f_{i,j,k} = \max f_{i-1,k,pre} + cnt_j $$
其中$pre$是枚举的能够与 $k$ 和 $j$ 合法存在于三行中的所有状态

初始状态：$f_{0,0,0}$
目标状态：$f_{n,j,k}\quad(其中j,k枚举的是所有合法的相邻状态)$

对于本题来说，直接开所有的状态空间，空间复杂度是 $O(N \times 2^M \times 2^M)$ 是会爆内存的

因此我们必须使用 滚动数组 进行优化

然后也可以预处理出来 相邻行之间的合法转移，也能避免掉一些不必要的不合法状态的枚举

Code

#include <iostream>
#include <vector>

using namespace std;

const int N = 110, M = 1 << 10;
int n, m;
int g[N], cnt[M];
int f[2][M][M];
vector<int> state;
vector<int> head[M];

bool check(int st)
{
    return !(st & st >> 1 || st & st >> 2);
}
int count(int st)
{
    int res = 0;
    while (st) res += st & 1, st >>= 1;
    return res;
}
int main()
{
    //input
    cin >> n >> m;
    for (int i = 1, j = 0; i <= n; ++ i, j = 0)
        for (char c; j < m && cin >> c; ++ j)   //纯属为了压行,没有其他意思w
            g[i] += (c == 'H') << j;
    //找出所有合法状态
    for (int st = 0; st < 1 << m; ++ st)
        if (check(st))
            state.push_back(st), cnt[st] = count(st);
    //找出所有合法状态的合法转移
    for (int cur_st: state)
        for (int pre_st: state)
            if (!(cur_st & pre_st))
                head[cur_st].push_back(pre_st);
    //dp
    for (int i = 1; i <= n; ++ i)
        for (int st: state)
            if (!(g[i] & st))
                for (int p1: head[st])
                    for (int p2: head[p1])
                        if (!(st & p2))
                            f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);
    //Enumerate the final state
    int res = 0;
    for (int st: state)
        for (int pre: head[st])
            res = max(res, f[n&1][st][pre]);
    //output
    cout << res << endl;
    return 0;
}

目标状态优化

思路同前两题一样，这里不做额外阐述

    for (int i = 1; i <= n + 2; ++ i)
        for (int st: state)
            if (!(g[i] & st))
                for (int p1: head[st])
                    for (int p2: head[p1])
                        if (!(st & p2))
                            f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);
    //output
    cout << f[n+2&1][0][0] << endl;

54 评论

Pokestar 2023-01-13 14:43

给各位大佬贴一个不用auto的代码

//彩笔大佬这里heap 存入对应的合法状态
//说明 head[][] :第一维是状态，第二维是读取的下标，它的值是第一维状态对应的合法状态
    for (int i = 1; i <= n; i++ ) 
        for (int j = 0; j < state.size(); j++ )
        {
            int a = state[j];
            if (!(g[i] & a))
                for (int k = 0; k < head[a].size(); k++) 
                {
                    int b = head[a][k];
                    if (!(g[i - 1] & b))
                        for (int u = 0; u < head[b].size(); u++ )
                        {
                            int c = head[b][u];
                            if ((a & c) == 0)
                            f[i & 1][a][b] = max(f[i - 1 & 1][b][c] + cnt[a], f[i & 1][a][b]);
                        }
                }
        }

Pokestar 2023-01-13 15:00

这里是f[2][i][ i - 1]

Xayanium 7个月前

自己的一些理解:
https://www.acwing.com/solution/content/239286/

lrs_0 7个月前

请问为什么要枚举到n+2行啊,多枚举一行不是到n+1行就可以了吗?

Xayanium 6个月前回复了 lrs_0 的评论

计算到n+2行其实是相当于对第n行和第n-1行的情况进行汇总，只计算到n+1的话，第n行的情况不能完全递推过去，可以打表查看数据

xushipeng 4个月前

佬，请问这为啥不对啊

for(int i=1;i<=n+2;i++){
        for(int j=0;j<state.size();j++){//第i
            for(int k=0;k<state.size();k++){//第i-1
                for(int u=0;u<state.size();u++){//第i-2
                    int a=state[j],b=state[k],c=state[u];
                    if((a&b)|(b&c)|(a&c))continue;
                    if(g[i]&a|g[i-1]&b|g[i-2]&c)continue;
                    f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][k][u]+cnt[a]);
                }
            }
        }
    }
    cout<<f[n+2&1][0][0];

baikun 8个月前

f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);
这句话为什么i&1 i-1&1 ？ &1是什么意思？

baikun 8个月前

滚动数组如果不开会爆空间复杂度

donaldqian 2023-06-15 18:13

%%%

Jesse_3 2022-04-20 19:13

求救！！为什么不能把两行合并起来当作一个状态啊

kistor 2022-04-21 19:26

应该可以吧，问了下同学得到了肯定的答复

Rsadj88 2个月前

count()函数用之前教的lowbit可以更快

int lowbit(int x){
    return x & (-x);
}
int count(int x){
    int ans = 0;
    while(x){
        x -= lowbit(x);
        ans ++;
    }
    return ans;
}

chenhaoze0423 7个月前

有个疑问：既然前i行的某个状态，是从前i-1行的某个状态转移而来，而且程序在出现转移方程之前已经排除了所有冲突行的情况，为何不能直接压缩掉转移方程的第3维？

HuRaymond 9个月前

巨巨,为什么p1不用于w[i - 1]判定是否合法

世蒂 2023-04-17 19:04

彩铅佬的代码总是如此的优雅呜呜呜

Fzldq 2022-10-21 09:34

Orz，小优化点：其实M开个70就够了，cols=10时只有60个合法状态

Littlecat 2022-05-27 22:10

Orz

种花家的小兔子 2022-03-31 15:36

巨巨，为什么这个滚动数组没有及时清空为0呢?

种花家的小兔子 2022-03-31 15:40

而且，题目要求求出最大值，那么为什么没把除了起点以外的点全部初始化为-INF？

一只野生彩色铅笔 2022-03-31 15:52 回复了种花家的小兔子的评论

第一个问题，状态值根据阶段 i 是非严格上升的，所有不初始化0和初始化0是等效的（必定更大）

所以也没有初始化负无穷的必要了，因为递增，所以必定会发生转移

种花家的小兔子 2022-03-31 15:58 回复了一只野生彩色铅笔的评论

就不会出现遍历到了非法情况(因为没有初始化为-INF,所以为0），但是此时还又另外加了cnt[st]，导致比当前值大吗？

f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);

一只野生彩色铅笔 2022-03-31 16:05 回复了种花家的小兔子的评论

if (!(g[i] & st)) 这一步判断了当前状态是否合法

上一层状态 f[i-1&1][p1][p2] 如果不合法，那值为0，这里就是 f[i&1][st][p1] = max(f[i&1][st][p1], cnt[st]);

相当于前面什么都没放，只在这一层摆放了 st

种花家的小兔子 2022-03-31 16:06 回复了一只野生彩色铅笔的评论

巨巨，这种额外加一个for循环，直接清空当前层的做法可取吗？(感觉这样就不用考虑那么多了）

   for (int i = 1; i <= n; ++ i)
    {
        for (int st: state)
        {
             for(int p1: head[st])
             f[i & 1][st][p1] = 0;
             if (!(g[i] & st))
             {
                 for (int p1: head[st])
                 {
                    for (int p2: head[p1])
                    {
                        if (!(st & p2))
                            f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);
                    }         
                }       
             }      
        }
    }