【排序 + 状态压缩背包】掷出重围

关键性质

对于已经选定的一组球，投掷顺序不会改变最终被占据的位置集合。

考虑交换两个相邻且落点逆序的球，它们的初始落点分别为 $a>b$。设从 $b$ 开始的第一个空位置为 $u$。

• 若 $u\<a$，从 $b$ 投出的球停在 $u$，不会影响从 $a$ 开始寻找空位。
• 若 $u\ge a$，那么区间 $\[b,u-1]$ 已经全部被占据。无论哪个球先投，第一个球都会停在 $u$，第二个球都会停在 $u$ 后面的第一个空位。

因此可以不断交换逆序的投掷，相当于按照 $w\_i$ 从小到大投掷。

将选择的球按照初始落点排序。假设上一个球最终停在 $p$，当前球的初始落点为 $w\_i$，那么当前球的最终位置为

$\max(w\_i,p+1).$

如果 $p\<w\_i$，它直接停在 $w\_i$。

如果 $p\ge w\_i$，上一个球的初始落点不超过 $w\_i$，而它能够滚动到 $p$，说明从 $w\_i$ 到 $p$ 的位置都已被占据，所以当前球停在 $p+1$。

朴素动态规划

可以把已经使用的体力和上一个球的最终位置都放入状态。

但 $w\_i$ 最大达到 $10^9$，不能直接将实际坐标作为数组下标。

关键在于：处理到当前落点 $w\_i$ 时，只需要知道上一个球比 $w\_i$ 多滚出了多少步。这个偏移量最多为选中球的数量，因此不超过 $n$。

这种把最后落点表示成相对当前 $w\_i$ 的偏移，并在相邻落点之间平移状态的做法，可以将复杂度控制在 $O(n^2s)$。(洛谷)

状态定义

首先把球按照 $w\_i$ 从小到大排序。

在处理第 $i$ 个球之前，定义 $f\_{j,k}$ 表示：

• 已经处理了前 $i-1$ 个球；
• 总体力消耗恰好为 $j$；
• 当前所有已选球的坐标和最大值；
• 上一个被投出的球相对于 $w\_i$ 的位置状态为 $k$。

其中：

• $k=0$：没有投出过球，或者上一个球的最终位置小于 $w\_i$；
• $k>0$：上一个球的最终位置为

$w\_i+k-1.$

只记录最大坐标和，因为状态相同的两个方案中，坐标和较小的方案不会更优。

初始状态为

$f\_{0,0}=0.$

其他状态均为负无穷。

投出当前球

设当前球消耗体力 $x\_i$。

如果原状态为 $k=0$，当前球停在 $w\_i$。

如果原状态为 $k>0$，上一个球停在 $w\_i+k-1$，当前球停在

$w\_i+k.$

两种情况可以统一写成：当前球最终停在 $w\_i+k$，新的偏移状态为 $k+1$。

因此转移为

$$f\_{j+x\_i,k+1} \max \left( f\_{j+x\_i,k+1}, f\_{j,k}+w\_i+k \right). $$

为了保证每个球最多选择一次，体力 $j$ 必须从大到小枚举。

不投出当前球时，状态不需要修改。

将基准移动到下一个落点

处理完第 $i$ 个球后，状态使用的坐标基准还是 $w\_i$。下一个球的基准为 $w\_{i+1}$。

记

$d=w\_{i+1}-w\_i.$

若当前 $k>0$，最后一个球的位置为

$w\_i+k-1.$

相对于新的基准 $w\_{i+1}$，新的偏移量为

$k-d.$

如果这个值不大于 $0$，说明最后一个球已经位于 $w\_{i+1}$ 左侧，具体位置不再重要，可以统一压缩为状态 $0$。

因此平移后的状态为

$k'=\max(0,k-d).$

对于多个状态平移到同一个 $k'$ 的情况，只保留坐标和最大的状态。

正确性说明

按照前面的交换论证，任意投掷方案都可以调整为按照 $w\_i$ 非递减的顺序投掷，同时最终占据的位置集合不变，因此排序不会遗漏最优方案。

处理第 $i$ 个球时，状态 $k$ 准确记录上一个球与当前初始落点的相对关系。

• 选择当前球时，其最终位置必然为 $w\_i+k$，所以选择转移准确模拟了滚动过程。
• 不选择当前球时，原方案仍然合法。
• 移动到下一个初始落点后，公式 $\max(0,k-d)$ 准确描述最后位置相对于新基准的偏移。当最后位置位于新基准左侧时，所有这类状态对后续球的影响完全相同，因此可以合并。

每个球只有选择与不选择两种转移，所有体力不超过 $s$ 的子集都会被处理。相同状态只保留最大坐标和不会丢失最优答案，因此最终得到的最大值就是答案。

参考实现

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

const int N = 505;
const ll inf = (1LL << 60);

int n, s;
pair<ll, int> a[N];
ll f[N][N], g[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
    }

    for (int i = 1; i <= n; i++) {
        cin >> a[i].second;
    }

    sort(a + 1, a + n + 1);
    a[n + 1].first = a[n].first;

    for (int j = 0; j <= s; j++) {
        for (int k = 0; k <= n; k++) {
            f[j][k] = -inf;
        }
    }

    f[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        ll w = a[i].first;
        int x = a[i].second;

        for (int j = s; j >= x; j--) {
            for (int k = 0; k < i; k++) {
                if (f[j - x][k] == -inf) {
                    continue;
                }

                f[j][k + 1] = max(
                    f[j][k + 1],
                    f[j - x][k] + w + k
                );
            }
        }

        ll d = a[i + 1].first - a[i].first;

        for (int j = 0; j <= s; j++) {
            for (int k = 0; k <= n; k++) {
                g[k] = -inf;
            }

            for (int k = 0; k <= i; k++) {
                if (f[j][k] == -inf) {
                    continue;
                }

                int t = (int)max(0LL, k - d);
                g[t] = max(g[t], f[j][k]);
            }

            for (int k = 0; k <= n; k++) {
                f[j][k] = g[k];
            }
        }
    }

    ll ans = 0;

    for (int j = 0; j <= s; j++) {
        for (int k = 0; k <= n; k++) {
            ans = max(ans, f[j][k]);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

排序的时间复杂度为 $O(n\log n)$。

动态规划中，每个球枚举体力和偏移量，选择转移与基准平移的复杂度均为 $O(ns)$，因此总时间复杂度为

$O(n^2s).$

动态规划数组大小为 $O(ns)$，空间复杂度为

$O(ns).$