Frog 3 题解

lottle1212 · 2023-05-09 22:22:05 · 题解

原题传送门

• Update on 2023.7.24，修复了图床。

Part 0

斜率优化本质上就是单调队列优化的升级版。

在学习斜率优化之前，请先熟练掌握单调队列优化。

Part 1

对于这一道题，我们很容易得出朴素 DP 的做法。不难发现：

于是我们可以先写下朴素 DP，以便对拍。

时间复杂度 O(n^2)。

TLE Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 2e5;
const int N = mxn + 10;
ll n, h[N], dp[N], C;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> C;
    for(int i = 1; i <= n; ++ i) cin >> h[i];
    for(int i = 2; i <= n; ++ i){
        dp[i] = 1e16;
        for(int j = 0; j < i; ++ j)
            dp[i] = min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + C);
    }
    cout << dp[n];
    return 0;
} 

Part 2

观察上面的动态转移方程，我们可以将 \min 以内的式子化简为：

其中，h_i^2, C 这些项与 j 无关，我们可以将其看作常量取出，则式子剩下：

而 dp_j, h_j^2 仅与 j 有关，设 \operatorname{f}(j) = dp_j + h_j^2，则式子变为：

再设 k = -2h_i，则：

至此，动态转移方程已化简完成。

Part 3

此时，设 j1 < j2，且 j2 不比 j1 优，仅当：

移项得：

两边同时除以 h_{j1} - h_{j2}，由于 h_{j1} - h_{j2} < 0，所以不等式要变号：

将 k = -2h_i 代入：

不等式两边同时乘 -1：

此时不等式的左边类似于求斜率的公式，故称为斜率优化。

Part 4

本文开头已经说过，斜率优化本质上是单调队列优化。因此，我们必须时刻维护队列中元素的单调性。

设 \operatorname{slope}(i, j) = \frac{\operatorname{f}(i) - \operatorname{f}(j)}{h_{i} - h_{j}}，表示 i, j 两点之间的斜率。

若有 pre, mid, nxt 三个节点，且 pre < mid < nxt，若使 mid 为最优决策点，必须满足：

表示不满足 pre 比 mid 优，且：

表示满足 mid 比 nxt 优，即：

这时，若有三点状态如下图：

通过观察，易得：

因此，2 号点一定不是最优决策点，我们可以将其删去。

最后，你会发现这东西就被维护成了一个凸包。

Part 5

当维护成一个凸包后，我们就可以对队列中的元素进行二分，找到斜率大于等于 2h_i 的最小节点，然后进行转移。时间复杂度 O(n \log n)。

但此题中，h 是一个递增序列，并不是无序的，因此，我们可以直接以单调队列的形式不断扔掉头元素，从而找到最优决策点，而无需二分。时间复杂度 O(n)。

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 2e5;
const int N = mxn + 10;
ll C, h[N], dp[N]; int head, tail, q[N], n;
double Y(int i) { return dp[i] + h[i] * h[i]; }
double X(int i) { return h[i]; }
double slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }//计算斜率
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> C;
    for(int i = 1; i <= n; ++ i) cin >> h[i];
    q[head = tail = 1] = 1;//单调队列初始化，青蛙原来在位置1
    for(int i = 2; i <= n; ++ i) {
        while(head < tail && slope(q[head], q[head + 1]) <= 2 * h[i]) ++ head; //若前两个元素不满足前一个元素更优，将前一个元素出队
        int j = q[head]; dp[i] = dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + C; //进行转移
        while(head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) -- tail; //维护凸包
        q[++ tail] = i; //入队
    }
    cout << dp[n];
    return 0;
}