CF505C题解

cheng_qi · 2022-11-06 10:17:05 · 题解

题意

给定 n 个有宝藏的点的坐标以及第一步的可以走的长度 d，求最多可以获得多少宝藏。（n,d\le 3 \times 10^4，坐标 \le 3 \times 10^4）

首先给人的感觉是一道贪心题，但是并没有什么好的贪心思路。对于这种每一步决策都对后续决策有影响的题目考虑DP，首先设 f_{i,j} 为走到坐标为 i，上一步走的长度为 j 获得的宝藏数。不难给出方程式：

其中 cnt_i 表示 i 坐标处有多少宝藏。

注意到数据范围，如果是 O(n\cdot d) 的时间复杂度一定过不去，我们考虑裁剪无效状态。

我们考虑有哪些状态才能被转移，假设第一次移动的步数为 d，最终的移动步数为 d + \lvert k\rvert ，根据等差数列 \frac{(d + d + \lvert k\rvert) \times (\lvert k \rvert + 1)}{2} \le 3\times 10^4，解得 \lvert k \rvert 不超过 400。因此我们可以删去大部分无用状态。时间和空间也就都在可接受范围内了。这道题本身不难，主要是如何判断哪些状态无用。

Code

在代码中贴了详细注释。

constexpr int N = 30005, D = 400;
int n, d, cnt[N], f[N][(D << 1) + 10];
int main() {
    // read 是快读，这里不给出实现
    read(n), read(d);
    for (int i = 1; i <= n; ++i) {
        int pos;
        read(pos);
        ++cnt[pos];//统计每个位置的宝藏数量
    }
    memset(f, -0x3f, sizeof(f));
    f[d][D] = cnt[0] + cnt[d];//考虑第一步走 d 步，于是初始状态直接设置在 d 位置
    // 我们将 D 看作零点，防止出现负下标
    int ans = 0;
    for (int i = d + 1; i <= 30000; ++i) {
        for (int j = -D; j <= D; ++j) {
            for (int k = -1; k <= 1; ++k) {
                int step = j + d + k; // 这一步的步长
                if (step < 1 || i + step > 30000 || j + k < -D || j + k > D)
                    continue;
                f[i + step][j + k + D] = max(f[i + step][j + k + D], f[i][j + D] + cnt[i + step]);//这个dp式子与朴素的dp式子是相同的
            }
            ans = max(ans, f[i][j + D]);
        }
    }
    write(ans);
    return 0;
}