自动搬运

查看原文

来自洛谷，原作者为

	Telesto 铃兰我老婆！IAKIOIIAKIOIIAKIOIIAKIOIIAKIOIIAKIOI

搬运于2025-08-24 22:19:53，当前版本为作者最后更新于2021-04-24 14:28:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

接雨雨

---

原题

题意：

我们有一个宽度为 $N$、高度无限的二维空间，以及 $N$ 个可爱的柱子。$(N\leq500)$

其中第 $i$ 个柱子宽度为 $1$，高度为 $a_i$，最高不会超过 $H$。$(H\leq50)$

我们可以在二维空间的底线上以任意顺序顺次放置柱子，注意不能扔掉任何一个柱子。

如果某个格子水平方向两侧都有柱子阻挡，那么此处就会积水。而地图边界最左与最右没有阻挡，不会产生积水。

---

重要结论：

对于某个柱子 x 上方的积水体积，可能产生的所有体积都是合法的。

---

HINT：

考虑在不含 x 的局面插入 x 。

---

HINT2：

让 x 与某个柱子交换。

---

证明：

我们最开始先放最高峰与第二高峰（因为她们俩一定不会在上方产生贡献），然后考虑在一个不含 $x$ 号柱子的局面插入 $x$ 号柱子能在其上方增加多少积水体积。

情况一：我们想让 $x$ 号柱子上方没有积水

我们找到在所有高度不大于 $x$ 号柱子、且上方没有积水的柱子里最低的那一个，设为 $y$。

我们再找到 $y$ 两侧中比 $y$ 更高的某个上方没有积水的柱子 $z$，将 $x$ 插在 $z$ 靠近 $y$ 的这一侧。

因为我们找到的 $y$ 是所有高度不大于 $x$ 号柱子、且上方没有积水的柱子里最低的那一个，因此 $z$ 高度一定大于等于 $x$ （不然找到的就该是 $z$ 了），于是这么插入不会产生新的积水。

首先在存在 $y$ 的情况中，因为最高峰的存在我们一定不会找不到 $z$。

其次如果不存在 $y$ ，那就证明所有不被积水覆盖的柱子都比 $x$ 高，那么我们可以将 $x$ 放置在最边界，这样也不会产生新的积水。

因此，在一个不存在 $x$ 的局面中插入 $x$ ，一定有存在一种方案使得插入后总贡献不变。

情况二：设某个比他高的柱子为 $y$ ，目标是使总贡献增加 $(a_y-a_x)$

1. 如果在该局面下，$y$ 并没有被积水覆盖

除让最高峰作为 $y$ 的情况外，一定可以插入到 $y$ 的一侧使得 $x$ 上方有 $(a_y-a_x)$ 体积的积水。

考虑 $y$ 两侧的积水高度，一定是要么两侧都比她低，要么是一侧比她低、一侧是自己的高度

而除了最高峰可以是两侧积水都比她自己低，其他柱子不可能产生这种情况（因为最高峰一定比她更高，如果没被积水覆盖，那她与最高峰之间的积水高度一定是她自己的高度）

2. 如果在该局面下，$y$ 被积水覆盖

那么我们就把 $y$ 所对应的位置换成 $x$，然后将 $y$ 按照情况一的方式处理。

假设 $y$ 的两侧离她最近的、那个较低的、没被积水覆盖的柱子为 $z$。

显而易见，$y$ 上方产生的贡献为 $(a_z-a_y)$ 。如果我们把 $y$ 换成 $x$ 显然不会影响其他柱子上方的积水，产生的新贡献为 $(a_z-a_x)$，总贡献与之前相比增加了 $(a_z-a_x)-(a_z-a_y)=(a_y-a_x)$。

3. 如果在该局面下，$y$ 未被插入

按照从大到小插入的方式就可以规避这种情况。

先处理 $y$ ，然后再处理 $x$。

因为一个更高的柱子产生贡献不可能依赖于更矮的柱子，所以这种产生贡献的依赖关系图是个有向无环图，并且只会有更低的柱子连向更高的柱子这种边。

我们按照从大到小的顺序插入就不会导致找不到 $y$。

---

综上，对于某个柱子 $x$ 上方的积水体积，可能产生的所有体积都是合法的。

有了这个结论我们就可以开始做了。 对所有柱子与比她高的柱子（除去最高峰）做差，然后进行个背包（注意：对于同一局面，某个柱子只能有一种添加贡献的方法），求出哪些值是可行的。枚举复杂度 $O(N^2)$,单次转移 $O(NH)$，总复杂度 $O(N^3H)$。显然有点大，但我们可以通过 bitset 优化背包，最终复杂度 $O(\frac{N^3H}{ω})$。

---

518B，简单又好写，跑得飞快。

#include<bits/stdc++.h>

using namespace std;

const int maxN=5e2+5,maxH=5e1+5;

int a[maxN];
bitset<maxN*maxH>dp,tem;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);
    dp[0]=true;
    for(int j=1;j<n;++j)
    {
        for(int st=j+1;st<n;++st)
        {
            tem|=(dp<<(a[st]-a[j]));
        }
        dp|=tem;
    }
    for(int i=0;i<=25000;++i)
    {
        if(dp[i])
        {
            printf("%d ",i);
        }
    }
}