# P17089 掷出重围 题解

## 题意分析

题目中有 $n$ 个球，每个球有两个属性：

- $w_i$：这个球被精准投掷后的初始落点。
- $x_i$：投掷这个球需要消耗的体力。

小 ζ 的总体力为 $s$，所以他不能随便把所有球都投出去，而是要从这些球中选择一部分，使得选中球的体力消耗总和不超过 $s$。

与普通背包不同，球的最终位置并不一定等于 $w_i$，如果一个球落在位置 $p$，而位置 $p$ 已经有球了，那么它会继续向前滚到 $p + 1, p + 2, \dots$，直到第一个没有球的位置。

因为小 ζ 可以任意决定投掷顺序，所以同一批被选择的球，不同投掷顺序可能会导致不同的最终位置分配。题目要求的是，在所有合法选择和投掷顺序中，使所有投出球的最终位置坐标之和最大。

## 10pts

仿照普通背包，设 $ans[i][j]$ 表示考虑前 $i$ 个球、体力不超过 $j$ 时，最终位置坐标和的最大值。

由于一个球落地后可能会继续向前滚，只记录最大和还不够，还需要知道当前方案已经占用了哪些位置。于是再使用一个 `set` 维护当前状态下已存在的球的位置：

```cpp
set<int> f[505][505];
long long ans[505][505];
```

其中 $f[i][j]$ 存储这个状态下所有球的最终停靠位置。

转移状态 $(i, j)$ 时，需要比较以下三种情况：

- 体力不超过 $j - 1$ 的最优方案，即状态 $(i, j - 1)$；
- 不选择第 $i$ 个球，即状态 $(i - 1, j)$；
- 选择第 $i$ 个球：若 $j \ge x_i$，从 $f[i - 1][j - x_i]$ 中的占用位置出发，找到从 $w_i$ 开始的第一个空位置 $tmp$。此时答案为 $ans[i - 1][j - x_i] + tmp$。

取三种情况中坐标和最大的方案，并同步保存其占用位置集合。

完整代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, s;
struct wx
{
    int w, x;
    inline const bool operator<(const wx a) const
    {
        return w > a.w;
    }
} ball[505];
set<int> f[505][505]; // 表示前i个球、有j的体力最远可扔的球的落地位置
long long ans[505][505]; // 球位置的和（可能超出int）
int main()
{
    scanf("%d %d", &n, &s);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &ball[i].w);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &ball[i].x);
    sort(ball + 1, ball + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= s; ++j)
        {
            if (ans[i][j - 1] > ans[i - 1][j])
            {
                ans[i][j] = ans[i][j - 1];
                f[i][j] = f[i][j - 1];
            }
            else
            {
                ans[i][j] = ans[i - 1][j];
                f[i][j] = f[i - 1][j];
            }
            if (j >= ball[i].x)
            {
                int tmp = ball[i].w;
                for (int k : f[i - 1][j - ball[i].x])
                {
                    if (k == tmp)
                        ++tmp;
                }
                if (ans[i - 1][j - ball[i].x] + tmp > ans[i][j])
                {
                    ans[i][j] = ans[i - 1][j - ball[i].x] + tmp;
                    f[i][j] = f[i - 1][j - ball[i].x];
                    f[i][j].insert(tmp);
                }
            }
        }
    }
    printf("%lld\n", ans[n][s]);
    return 0;
}
```

提交，喜提10ptsMLE

![提交记录](https://cdn.luogu.com.cn/upload/image_hosting/msubiito.png)

这个做法最大的问题是空间太大。

$n, s \le 500$，二维状态有大约 $500 \times 500 = 250000$ 个。每个状态还存一个 `set`，而每个 `set` 里面又可能有很多位置。

所以空间复杂度接近：

$$ O(n^2s) $$

而且 `set` 本身还有较大的常数开销，实际运行时非常容易内存爆炸。

## 优化

注意到背包转移中，第 $i$ 个球只会从上一轮状态转移过来，因此可以使用滚动数组。

把：

```cpp
set<int> f[505][505];
long long ans[505][505];
```

改成：

```cpp
set<int> f[505];
long long ans[505];
```

其中 $f[j]$ 表示当前处理到某个球时，体力不超过 $j$ 的最优方案所占用的位置集合。

选择当前球时，需要倒序枚举体力：

```cpp
for (int j = s; j >= ball[i].x; --j)
```

这样可以保证每个球只被选一次。

## 最终思路

对于每个球，倒序枚举体力 $j$：

1. 从状态 $j - x_i$ 转移过来。
2. 在该状态的占用位置集合中，从 $w_i$ 开始找第一个空位置 $tmp$。
3. 如果选择当前球后答案更优，就更新 $ans[j]$ 和 $f[j]$。

每轮处理完一个球后，再由小到大枚举 $j = 1 \dots s$，若 $ans[j - 1]$ 更优，则用 $ans[j - 1]$ 更新 $ans[j]$。

## 复杂度分析

滚动数组中有 $O(s)$ 个状态，每个状态保存一个最多含 $O(n)$ 个位置的 `set`，因此空间复杂度为 $O(ns)$。

每次转移需要遍历一个 `set` 寻找落点，并且在更新时复制该 `set`，两者最坏均为 $O(n)$。一共有 $O(ns)$ 次转移，因此时间复杂度为 $O(n^2 s)$。

## AC代码

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, s;
struct wx
{
    int w, x;
    inline const bool operator<(const wx a) const
    {
        return w > a.w;
    }
} ball[505];
set<int> f[505]; // 有j的体力时，当前最优方案中球的最终落点
long long ans[505]; // 有j的体力时，当前最优方案的坐标和
int main()
{
    scanf("%d %d", &n, &s);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &ball[i].w);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &ball[i].x);
    sort(ball + 1, ball + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = s; j >= ball[i].x; --j)
        {
            int tmp = ball[i].w;
            for (int k : f[j - ball[i].x])
            {
                if (k == tmp)
                    ++tmp;
            }
            if (ans[j - ball[i].x] + tmp > ans[j])
            {
                ans[j] = ans[j - ball[i].x] + tmp;
                f[j] = f[j - ball[i].x];
                f[j].insert(tmp);
            }
        }
        for (int j = 1; j <= s; ++j)
        {
            if (ans[j - 1] > ans[j])
            {
                ans[j] = ans[j - 1];
                f[j] = f[j - 1];
            }
        }
    }
    printf("%lld\n", ans[s]);
    return 0;
}
```