BZOJ2216: [Poi2011]Lightning Conductor

第一道此類的題，所以這是一篇假的博客，定理不會證明不理性

也不一定對

我是從這篇博客看的 = =?

很顯然是讓你求 p[i] = max{a[j] + sqrt(i - j)} - a[i]

就是?max{a[j] + sqrt(|i - j|)}

這是一個 1D/1D 動態規劃

?

考慮對于絕對值的情況不好做，那就強行去掉絕對值
之后正反各做一遍

設 sqrt(i - j) 為 w[j, i]

它顯然滿足區間包含單調性，考慮證明它滿足四邊形不等式

設 j < j + 1 < i < i + 1

應該是 w[j, i] + w[j + 1, i + 1] 與 w[j + 1, i] + w[j, i + 1] 的關系

由于函數 y = sqrt(x) 的圖像是斜率遞減的

所以顯然有 w[j, i] + w[j + 1, i + 1] > w[j + 1, i] + w[j, i + 1] ①

考慮決策單調性，設對 i 有 a[j + 1] + w[j + 1, i] > a[j] + w[j, i] ②

① + ② 得 a[j + 1] + w[j + 1, i + 1] > a[j] + w[j, i + 1]

所以若對 i 成立對 i + 1 也成立

所以決策點是單調的

?

那么整個序列每個位置對應的最優決策點組成的序列應該是這樣:

111133336666....

可以用隊列來維護它，隊列中存三元組 (l, r, id)?
表示 id 這個決策點能更新的區間為 [l, r]

?

實際操作起來是這樣的：

考慮當前點 i 的影響，若它能比之前的一些點優，
它一定是將整個序列從某一個位置開始到 n 的最優決策點

那么它能比之前點優的條件就是對于 n ，當前點比隊尾優

然后會有一些決策點被當前點廢掉，
條件就是對于一個決策點 p , 若在它能更新的區間左端點 l 處, i 比 p 優，
則這個點沒有用了

那么若隊列未被彈空，最后剩下的隊尾一定是滿足在它的 l 處 它比 i 優

r 就不一定了，這里在隊尾的 [l, r] 中二分第一個 i 比 id 優的位置，設為 dst

那么隊尾的 r 就要改成 dst - 1

并將 i 入隊，區間為 [dst, n]

---

代碼：

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<cmath>
using namespace std;const int MAXN = 500005;struct INFO{int l, r, id;INFO(int L = 0, int R = 0, int ID = 0) {l = L; r = R; id = ID;}
}q[MAXN];
int n, hd, tl;
int a[MAXN], b[MAXN];
double f1[MAXN], f2[MAXN];inline int rd() {register int x = 0;register char c = getchar();while(!isdigit(c)) c = getchar();while(isdigit(c)) {x = x * 10 + (c ^ 48);c = getchar();}return x;
}
inline int hfs(int l, int r, int bck, int cur, int *arr) {register int mid = 0, ans = l;while(l <= r) {mid = ((l + r) >> 1);if((double)arr[bck] + sqrt(mid - bck) < (double)arr[cur] + sqrt(mid - cur)) {ans = mid;r = mid - 1;} else l = mid + 1;}return l;
}
inline void work(int *val, double *f) {hd = 1; tl = 0;q[++tl] = INFO(1, n, 1);for(int i = 2; i <= n; ++i) {++q[hd].l;//printf("i = %d, hd = %d, tl = %d\n", i, hd, tl);while(hd <= tl && q[hd].r < q[hd].l) ++hd;if((tl < hd) || ((double)val[i] + sqrt(n - i) > (double)val[q[tl].id] + sqrt(n - q[tl].id))) {while(hd <= tl && ((double)val[i] + sqrt(q[tl].l - i) > (double)val[q[tl].id] + sqrt(q[tl].l - q[tl].id))) --tl;if(tl < hd) {q[++tl] = INFO(i, n, i);} else {register int dst = hfs(q[tl].l, q[tl].r, q[tl].id, i, val);q[tl].r = dst - 1;q[++tl] = INFO(dst, n, i);}}f[i] = (double)val[q[hd].id] + sqrt(i - q[hd].id) - val[i];}return;
}int main() {n = rd();for(int i = 1; i <= n; ++i) a[i] = b[n - i + 1] = rd();work(a, f1);work(b, f2);for(int i = 1; i <= n; ++i) printf("%d\n", max(0, (int)ceil(max(f1[i], f2[n - i + 1]))));return 0;
}