UTS Open '21 P6 - Terra Mater

标签：le P6 21 danger int Terra ge times dp

传送门

前言

本题是一道很好的“dp”题，无论是正难反易，还是模型转化都值得称赞，尤其是最后的神之一手，让我大脑宕机。

题意描述

给定一个长度为 \(N\) 的序列 \(H\)，修改不超过 \(K\) 个数，使得 \(\max_{1}^{N - 1}{H_{i + 1} - H_i}\) 最小。
\(2 \le N \le 2 \times 10^5\) ，\(0 \le K \le N\) ，\(1 \le H_i \le 10^9\)

思路推导 & 做法

首先，对于这一类最大值最小的问题，我们有一个模板化的思考方向——二分答案，在尝试后，发现对于该题在确定答案后再判断是否有解是有用的，因为答案限制了相邻 \(H_i\) 的取值，同时并没有什么可贪心或能转化为图论的地方，所以考虑 \(\text{dp}\) check。
然后怎么做呢？在思考良久后，发现这道题很难（这不废话吗），连暴力 \(\text{dp}\) 都打不出来。直接硬做做不出来，就要思考如何把题目进行转化以降低难度。此时就要发挥你惊人的注意力，像瞪几何大题一样敏锐地发现直接做做不出来的原因在于若该修改 \(i\) 你在 \(i + 1\) 就不知道上一个选了什么数也无法定义进状态里，所以就要把从某个地方转移过来的数固定下来，所以就要将“不修改”放进 \(\text{dp}\) ，也就是正难反易，于是定义 \(dp_i\) 表示考虑完前 \(i\) 座山丘，第 \(i\) 座山丘不修改，最多能有多少座山丘不修改。
考虑状态转移，设二分的答案为 \(danger\)，若 \(2\) 座山丘 \(i, j (j < i)\) 都不修改，则要满足对于山丘 \(k \in (j, i)\) 都修改的情况下，也就是最容易满足的情况下能满足条件，即 \(|H_i - H_j| \le danger \times (i - j)\) 。所以有如下 \(\text{dp}\) 转移式：

\[dp_i = \max_{j \in [1, i) \wedge |H_i - H_j| \le danger \times (i - j)}{dp_j + 1} \]

目前我们有了 \(O(N^2 \log {10^9})\) 的做法，但这明显不够，所以我们要把 \(\text{dp}\) 优化进 \(O(N \log N)\) 及以内。
现在我们要从状态转移方程入手，发现其中最不规整也最难优化的是 \(|H_i - H_j| \le danger \times (i - j)\) 这一个条件，绝对值的存在让我们不能轻易优化，所以要拆绝对值，条件就变成了

\[H_i - H_j \le danger \times (i - j) \wedge H_j - H_i \le danger \times (i - j) \]

再将具有同一变量的值移到同侧，变为

\[danger \times j - H_j \le danger \times i - H_i \wedge danger \times j + H_j \le danger \times i + H_i \]

发现所有与 \(j\) 有关的和与 \(i\) 有关的都分列两侧，所以可以另定义权值，把条件变漂亮。定义 \(X_i = danger * i\) ，定义 \(v_i \ge v_j\) 为 \(X_i - H_i \ge X_j - H_j 且 X_i + H_i \ge X_j + H_j\) （这式子好整齐啊，要不是我推出来的一定还有转化），反之为 \(\le\) ，问题就转化为给定长度为 \(n\) 的序列 \(v\) ，求该序列的最长不下降子序列 。
当你做到这一步时大抵是会欣喜若狂像我一样 ，以为马上就切掉这道题了，但好题就是好题，总在你得意忘形时给你沉重一击（笑容凝固）。你惊世骇俗地发现加上 \(i\) 这一维下标后就变成了三维偏序，解决的经典办法是CDQ分治或二维树状数组，但 \(O(N \log^2 N)\)，总时间 \(O(N \log^2 N log 10^9)\) ，然后你的动作be like：Win + R ——calc——\(200000 \times (\frac{log_{10}^{200000}}{log_{10}^{2}})^2 \times \frac{log_{10}^{10^9}}{log_{10}^{2}} = 1854230461.3827186693864795412925\dots\) ，随即亲切地问候了出题者的祖宗苦思冥想，始终不得其解。

神之一手

我翻开算法圣经（蓝本）一查，这三维偏序没有界限，歪歪斜斜的每页上都写着CDQ分治几个字。我横竖想不通，仔细看了半日，才从字缝里看出来，满本都写着两个字是 \(O(N \log^2 N)\)！

当你接近崩溃的时候，你忽地想起了推出的式子和心中的想法，抱着试一试的心态去推了一下式子进行转化（回收伏笔），脑袋里还想着什么高深算法，把三减个一变成二，突然发现答案就在笔下。
若 \(v_j \ge v_i (j < i)\) ，则

\[X_j - H_j \ge X_i - H_i \]

\[X_j + H_j \ge X_i + H_i \]

变形得

\[H_i - H_j \ge X_i - X_j \]

\[H_i - H_j \le X_j - X_i \]

将 \(X_i,X_j\) 还原回去

\[H_i - H_j \ge danger \times (i - j) > 0 \]

\[H_i - H_j \le danger \times (j - i) < 0 \]

\[矛盾! \]

所以我们可以得出若 \(j < i\) ，\(v_j \le v_i\) ，所以当交换 \(v_j, v_i\) 后（权值不变），\(dp_i\) 一定不对 \(dp_j\) 产生贡献，所以交换两个数后答案一定不会变大。
若 \(v_i \ge v_j (j < i)\) ，则

\[X_i - H_i \ge X_j - H_j \]

\[X_i + H_i \ge X_j + H_j \]

由此得出如果按某一维排序后 \(dp_j\) 仍然在 \(dp_i\) 前且一定满足 \(v_i \ge v_j\) ，\(dp_i\) 仍然可以从 \(dp_j\) 转移，所以原本可转移的方向现在仍然存在，故排序后答案不会变小。
交换 \(v_i, v_j\) 后答案不变大又可以缩小范围为对 \(v\) 排序后答案不变大，此时答案也不变小，所以任意按某一维排序后答案不变！！！
这神之一手直接把索引 \(i\) 的一维砍掉，成功把三维偏序转化为二维偏序，直接用 \(\text{LIS}\) 模板树状数组即可。

solution

思路想通后代码异常简单。

/*
address:https://dmoj.ca/problem/utso21p6
AC 2025/1/11 16:49
*/
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
const int N = 2e5 + 5;
int n, k;
int h[N];
struct BinaryTree {
    int c[N];
    inline void init(int n) { fill(c + 1, c + n + 1, 0); }
    inline void change(int x, int k) { for (;x <= n;x += lowbit(x)) c[x] = max(c[x], k); }
    inline int query(int x) {
        int ret = 0;
        for (;x > 0;x -= lowbit(x)) ret = max(ret, c[x]);
        return ret;
    }
}BIT;
typedef long long LL;
pair<LL, LL>a[N];
LL disc[N];
int dp[N];
inline bool check(int danger) {
    BIT.init(n + 1);
    for (int i = 1;i <= n;i++) a[i] = { 1ll * danger * i - h[i],1ll * danger * i + h[i] };
    sort(a + 1, a + n + 1);
    for (int i = 1;i <= n;i++) disc[i] = a[i].second;
    sort(disc + 1, disc + n + 1);
    int m = unique(disc + 1, disc + n + 1) - disc - 1;
    for (int i = 1;i <= n;i++) a[i].second = lower_bound(disc + 1, disc + m + 1, a[i].second) - disc;
    for (int i = 1;i <= n;i++) {
        dp[i] = BIT.query(a[i].second) + 1;
        BIT.change(a[i].second, dp[i]);
    }
    for (int i = 1;i <= n;i++)
        if (dp[i] >= n - k) return true;
    return false;
}
int main() {
    int T;scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1;i <= n;i++) scanf("%d", &h[i]);
        int l = 0, r = 1e9, ans = 1e9;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid - 1, ans = mid;
            else l = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

总结

这道题单说前几步难度就已经很大了，最后出题者的阴险巧妙构思画龙点睛，让这道题的难度更上一层。这种巧妙的题还是少见，值得珍惜。
同时也明白了莫要

只言片语尽显高见, 行动却似矮人观场

标签：le,P6,21,danger,int,Terra,ge,times,dp
From： https://www.cnblogs.com/keysky/p/18678669