BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

题意

题目链接

Sol

很nice的决策单调性题目

首先把给出的式子移项，我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

按套路把绝对值拆掉，$p_i = max(max_{j = 1}^i (a_j = \sqrt{i - j}), max_{j = i + 1}^n (a_j + \sqrt{j - i})) - a_i$

对于后面的一段，我们把序列翻转之后和前一段是等价的。

也就是说，我们现在只需要找到$P_i = max_{j = 1}^i (a_j +　\sqrt{i - j})$

考虑到式子中只有一个max函数，那这玩意儿应该是有决策单调性的

直接设$f_j = a_j + \sqrt{i - j}, i \geqslant j$，其中$i$是自变量

观察这个函数，应该是一个在$[j, INF]$内有定义，过点$(j, a[j])$的函数，且增速与函数$g_i = \sqrt{i}$相同

我们需要做的，就是对每个$i$，找到最大的$f_j$

考虑到$g_i$增长速度会越来越慢，所以一个函数增长到一定程度后可能会被另一个函数取代

直接用单调队列维护，设$K_{i, j}$表示$f_i, f_j$的交点，$h, t$分别表示队首/尾，

当新加入一个元素$i$的时候，显然，若$K_{t -1, t} > K_{t - 1, i}$，那么$t$这个函数是没用的、

当$K_{h, h+1} < i$的时候，弹出队首

就是最后输出答案的时候有点“卡精度”，真恶心

经验：

以后看到$f_i = max(f_j) + g$的式子一定要往单调性上想，如果单调性不是很显然的话可以用换元法设函数找单调性

另外绝对值拆开算一般会好算一些

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], q[MAXN], Cro[MAXN];
double P[MAXN], sqr[MAXN];
double calc(int j, int i) {
    return a[j] + sqr[i - j];
}
int K(int x, int y) {
    int l = max(x, y), r = N, ans = N + 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(calc(x, mid) >= calc(y, mid)) l = mid + 1;
        else r = mid - 1, ans = mid;
    }
    return ans;
}
void solve() {
    int h = 1, t = 0;
    for(int i = 1; i <= N; i++) {
        while(h < t && K(q[t - 1], q[t]) >= K(q[t], i)) t--;
        q[++t] = i;
        while(h < t && K(q[h], q[h + 1]) <= i) h++;
        P[i] = max(P[i], calc(q[h], i));
    }
}
main() {
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read(), sqr[i] = sqrt(i);
    solve();
    reverse(a + 1, a + N + 1);
    reverse(P + 1, P + N + 1);
    solve();
    for(int i = N; i >= 1; i--)
        printf("%d\n", max(0, (int)ceil(P[i]) - a[i]));
    return 0;
}