P8484 Mole 题解

鏡音リン · 2022-08-24 19:43:07 · 题解

考虑 dp。

我们记 D[x][y] 表示，前 x 个数共选了 y 次的答案。

根据题意，状态有意义的范围为 x-l+1\le y\le x。

转移就是枚举第 x 个数选了 k 次，那么

直接枚举 k 转移当然是 n^3。

有同学这里会说，我会斜率优化啊，n^2 啊。

斜率优化没错……但是你学傻了……

这玩意可以看作 D[x] 是 D[x-1] 和一个二次函数的加max卷积，两边都是凸函数，所以这个卷积叫做闵可夫斯基和。

没听过的话我直接放结论，两个数组做闵可夫斯基和，答案的差分数组是它俩的差分数组的归并。

（至于为啥 D 是凸的，你归纳法假设 D[x-1] 是凸的，那么卷积的结果 D[x] 当然还是凸的）

于是直接用这玩意转移复杂度 n^2。

实现的时候发现，既然是差分归并，那直接维护 D 的差分不就好了。定义 dp[x][y] = D[x][y+1] - D[x][y]，然后不停地归并 \{a[x],a[x]-1,a[x]-2,\dots\} 这样的数组就好了。

当 x 逐渐增大的时候，较小的 y 值会变得不合法，直接把最左边的 dp 值删掉计入答案就行。

放个 60 分核心代码（去掉了头文件和快读）：

#define N 5001
int dp[2][N], cnt, l, n; long long ans;
int main() {
    rint(l); rint(n);
    for (int i = 0, x; i < n; i++) {
        rint(x);
        int L = std::max(i-l+1, 0);
        for (int j = L, p = L; j <= i && j <= n-l+1; j++)
            dp[cnt][j] = dp[!cnt][p] > x ? dp[!cnt][p++] : x--;
        if (i >= l-1) printf("%lld ", ans += dp[cnt][L]);
        cnt = !cnt;
    }
}

考虑优化，想想我们对 dp 数组干了啥。我们记 dp 组成的多重集合是 S。由于这玩意必定是有序的，所以维护集合和数组没区别。

每一步相当于：

1. 把 a[x],a[x]-1,\dots,1 的所有值加入 S
2. 保留 S 中最大的 l 个数字，其它的删掉
3. 如果此时窗口已经开始滑动了，把 S 中最大的再删掉并计入答案

那么记 b[x] 为 x 在 S 内的出现次数。上述三个操作对 b 的影响是：

1. 前缀所有位置 +1
2. 二分一个前缀和，然后前缀清零（可能有一次单点修改）
3. 找到最大值位置并 -1

这些操作都是线段树可以维护的。复杂度 n\log n。代码就不放了。