[CCO 2017]接雨滴(2021/11/19)

· · 题解

接雨雨

原题

题意：

我们有一个宽度为 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 两侧的积水高度，一定是要么两侧都比她低，要么是一侧比她低、一侧是自己的高度

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

  1. 如果在该局面下，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)。

  1. 如果在该局面下，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);
        }
    }
}