击杀 题解

题目大意

$n\times m$ 网格，有若干幽灵，第 $i$ 只位于坐标 $(x_i,y_i)$、能力值 $A_i$。从左侧任意位置进入，每单位时间向右走 1 格，纵向每单位时间可移动 $[-delta,delta]$；经过幽灵坐标即击杀。求击杀幽灵能力值之和的最大值。

算法思路

把每只幽灵看成一个点。若两只幽灵能先后被同一路径击杀，则纵向位移不能超过 $delta\times$ 横向位移。

按"前进方向"坐标（纵向坐标）排序后，问题变成在 DAG 上求最大权路径（类 LIS）：

$$f[i]=A_i+\max_{j<i,\ |y_i-y_j|\le delta\cdot(x_i-x_j)} f[j]$$

排序后 $x_i\ge x_j$，转移条件即 $|y_i-y_j|\le delta\cdot(x_i-x_j)$。答案为 $\max f[i]$。

复杂度

$O(n^2)$（$n\le 4000$）。

补充

如果 $n$ 达到 $10^5$ 级别，可以使用单调队列优化dp，复杂度 $O(nm)$ 。但是这种做法请使用手写双端队列，deque存在卡常

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Ghost { int x, y; ll v; };  // x=第一个坐标，y=第二个坐标(排序依据)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, delta, num;
    cin >> n >> m >> delta >> num;
    vector<Ghost> g(num);
    for (auto &e : g) cin >> e.x >> e.y >> e.v;

    sort(g.begin(), g.end(), [](const Ghost &a, const Ghost &b) { return a.y < b.y; });

    vector<ll> dp(num, 0);
    ll ans = 0;
    for (int i = 0; i < num; ++i) {
        dp[i] = g[i].v;
        for (int j = 0; j < i; ++j) {
            if (abs(g[i].x - g[j].x) <= 1LL * delta * (g[i].y - g[j].y)) {
                dp[i] = max(dp[i], dp[j] + g[i].v);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0;
}