2024杭电多校（2）B. 梦中的地牢战斗 【状压、最短路、dp】

题意

在一张 $n\times m$ 的地图上，有 $K$ 个怪物在不同的位置，每个怪物有三个属性：价值 $A_i$、攻击力 $B_i$、攻击距离 $C_i$
角色初始生命值为 $1$，且一开始出现在 $(sx,sy)$ 位置，在进入地牢前可以花费 $x$ 个（$x$ 为任意正整数）金币来获得 $x$ 点生命值，也可以选择不贷款。注意这个操作只能在进入地牢前进行，进入地牢后将无法购买生命值

本题的距离为曼哈顿距离

每回合开始，可以选择以下两个操作之一：

1. 离开地牢，获得当前击杀怪物的价值并结算
2. 瞬移到同行/同列与当前距离不超过 $d$ 的没有怪物的地图内的位置，并击杀瞬移起点和终点的所有怪物，获得一定收益。同时，在瞬移结束后，所有距离角色不超过其攻击距离的怪物会攻击角色，如果角色生命值小于等于 $0$，则游戏结束，且失去所有金币

问主角最多可以获得多少金币？（击杀怪物的收益减去一开始贷款购买生命值的花销）

$2\le n,m\le 30,1\le K\le 10$
瞬移距离 $1\le d\le 8$
$1\le A_i、B_i、C_i\le 10^4$

思路

注意到 $K$ 很小，我们可以用 $2^{10}$ 的状态压缩来表示怪物的存活/击杀情况
并且，对于一开始的贷款机制，我们转换一下思路，我们可以允许游戏过程中生命值为负，直接把怪物的攻击看成扣金币，这样子算出来的一个最大的金币方案，其实就是最终的答案。
这是因为我们已经“预先”知道了要贷款多少生命值，已经知道了方案。其实就是欠费的思想

这样子 $DP$ 状态可以设置成 $d{p}_{x,y,s}$ 表示当前在位置 $(x,y)$ 且怪物击杀情况为 $s$ 时（$0$为未击杀，$1$为已击杀）的最大金币数量

后面就可以枚举转移了，如果把 $(x,y,s)$ 抽象成点，我们其实就等价于在这张图上面跑每个状态的最长路。

进一步观察，我们会发现这张图很特殊，首先图是没有正环的，原因很简单（不可能不击杀怪物还能获得金币），但是可能存在负环。
并且如果我们以 $s$ 分层（小的在上，大的在下），我们会发现：只会有从上指向下的有向边，不可能存在下到上的边（因为怪物不能复活）
这样子其实就可以分层来 拓扑$DP$，但是同一层的内部，可能会有负环和负边（不会有正边，因为没有击杀怪物），我们需要在这一层内部，跑一个最长路，其实就是最短路反过来就可以了，这样子就保证了 $DP$ 的最优子结构这一特性

之所以前面要用 $1$ 来表示已击杀的怪物，而不是还存活的怪物，是因为方便从小到大枚举已击杀怪物的集合，方便 $dp$ 转移

时间复杂度：$(nm{2}^{K}d\cdot \log (nm{2}^K))$

#include<bits/stdc++.h>
#define fore(i,l,r)for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

const int N = 35;
const int K = 10;

int mp[N][N];
int n, m, k;
int d; //瞬移距离上限
std::vector<std::pair<int, int>> mv = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

struct Mos{
    int x;
    int y;
    int c;
    int atk;
    int len;
};

Mos mos[K + 5];
int dp[N][N][1 << K]; //1表示已击杀
int cost[N][N][1 << K]; //到某个位置落脚的花销

bool check(int x, int y){
    return x >= 1 && x <= n && y > 0 && y <= m;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while(t--){
        std::cin >> n >> m >> k;
        fore(i, 1, n + 1)
            fore(j, 1, m + 1){
                mp[i][j] = k + 5; //没有怪物
                fore(s, 0, 1 << k){
                    dp[i][j][s] = -INF; //收益
                    cost[i][j][s] = 0; //花销
                }
            }
        std::cin >> d;
        fore(i, 0, k){
            std::cin >> mos[i].x >> mos[i].y >> mos[i].c >> mos[i].atk >> mos[i].len;
            mp[mos[i].x][mos[i].y] = i; //编号
        }

        int sx, sy;
        std::cin >> sx >> sy;
        dp[sx][sy][0] = 0;
        int ans = 0;

        /* 初始化花销 */
        fore(i, 1, n + 1)
            fore(j, 1, m + 1)
                fore(s, 0, 1 << k)
                    fore(p, 0, k){
                        if(s >> p & 1) continue; //已击杀
                        auto [x, y, c, atk, len] = mos[p];
                        int dis = std::abs(x - i) + std::abs(y - j);
                        if(dis > len) continue; //距离太长，无法攻击
                        cost[i][j][s] += atk;
                    }
        
        auto solve = [&](int S){
            std::priority_queue<std::tuple<int, int, int>> q; //大根堆
            fore(i, 1, n + 1)
                fore(j, 1, m + 1)
                    if(dp[i][j][S] > -INF)
                        q.push({dp[i][j][S], i, j});
            
            std::vector<std::vector<bool>> vis(n + 1, std::vector<bool>(m + 1, false));
            
            while(!q.empty()){
                auto [val, x, y] = q.top();
                q.pop();
                if(vis[x][y]) continue;
                vis[x][y] = true;
                ans = std::max(ans, dp[x][y][S]);
                for(auto [dx, dy] : mv){
                    int pass = 0, tot = 0; //经过怪物集合、收入
                    fore(i, 1, d + 1){
                        int xx = x + i * dx, yy = y + i * dy;
                        if(!check(xx, yy)) break;
                        if(mp[xx][yy] < k && !(S >> mp[xx][yy] & 1)){ //有怪物且还没击杀
                            pass |= 1 << mp[xx][yy];
                            tot += mos[mp[xx][yy]].c;
                        }
                        else if(!pass){ //路上没有怪物，同层节点转移
                            int n_val = val - cost[xx][yy][S];
                            if(dp[xx][yy][S] < n_val){
                                dp[xx][yy][S] = n_val;
                                q.push({n_val, xx, yy}); //更大价值
                            }
                        }
                        else{
                            dp[xx][yy][S | pass] = std::max(dp[xx][yy][S | pass], 
                                    val + tot - cost[xx][yy][S | pass]);
                        }
                    }
                }
            }
        };
        
        fore(S, 0, 1 << k) solve(S); //从小到大枚举已击杀怪物的集合

        std::cout << ans << endl;
    }
    return 0;
}

原文地址：https://blog.csdn.net/m0_73500785/article/details/140645047

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！