[BZOJ 2216][Poi2011] Lightning Conductor DP

题目大意

已知一个长度为n的序列a1,a2,…,an。
对于每个1<=i<=n,求最小的非负整数p满足 对于任意的j,aj < = ai + p – sqrt(abs(i-j))

解题报告

测试数据福利:

Input:
40
141
125
12
5
21
4523
5
245
1245
24
23
4234523
4
13
423
41
41
24
124
235
12
4523
34
123
24
234
23
341
412
34
12
423
5
1234
124
12
412
34
123
12
Output:
4234386
4234402
4234514
4234521
4234505
4230003
4234521
4234280
4233280
4234501
4234501
0
4234520
4234512
4234102
4234484
4234485
4234502
4234402
4234291
4234514
4230004
4234493
4234404
4234503
4234293
4234504
4234186
4234116
4234494
4234516
4234105
4234523
4233294
4234404
4234516
4234116
4234495
4234406
4234517
(我是不会告诉你输入是滚键盘打出来的~(笑))

考虑dp
因为sqrt(i-j)这个函数的导不停地减小，所以这里的决策具有单调性。
比如对于两个位置p和q,p < q,假如p从i转移过来,q从j转移过来,i一定会小于j
那么，如果对于i位置的最优决策点，如果有p < q并且从q点转移到i点优于p点转移到i点,那么p点对于i和大于i的位置的转移必然已经毫无用处了。从q点转移到任何大于等于i的点必然会比从p点转移更好
举个栗子:
[不好!博客搬家时图挂了!]
图中蓝色部分从i=1转移是最好的。但是由于函数的斜率不停降低，加之i=2的开始位置较高(a[2] > a[1])
绿色部分就从i=2转移最好。由于i=3的开始位置(a[3])太低，没有任何一个位置从3转移最好。黄色部分从i=4转移最好。
那么就可以有这么一个想法:
假如当前扫到了位置i
1.用一个单调队列维护i之前的最优决策点
2.用队首和次级队首比较，如果次级队首更优，那么弹出队首，如此重复得到最优队首
3.用队首更新i处dp值
4.同理从队尾弹掉比i不优的决策点
5.把i加入队尾
6.i++
正向跑一次，在反向跑一次，dp值取max即可。
于是。。我成功用这份 错误的思路 yy出了一份错误的代码。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
const int MAXN = 501000;
int arr[MAXN], sqr[MAXN+100000], ans[MAXN];
int seq[MAXN];
int main () {
    int N;
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%d", &arr[i]);
    for(int j = 1; (j-1)*(j-1)<=550000; j++) {
        int r = j*j;
        for(int i = (j-1)*(j-1)+1; i<=r; i++)
            sqr[i] = j;
    }
    int l = 0, r = -1; seq[++r] = 1;
    for(int i = 2; i<=N; i++) {
        while(l < r && arr[seq[l]]+sqr[abs(i-seq[l])] < arr[seq[l+1]]+sqr[abs(i-seq[l+1])]) l ++;
        ans[i] = std :: max(ans[i], arr[seq[l]]-arr[i]+sqr[abs(i-seq[l])]);
        while(l <= r && arr[seq[r]]+sqr[abs(i-seq[r])] < arr[i]) r --;
        seq[++ r] = i;
    }
    std :: reverse(arr+1, arr+N+1);
    std :: reverse(ans+1, ans+N+1);
    l = 0, r = -1; seq[++r] = 1;
    for(int i = 2; i<=N; i++) {
        while(l < r && arr[seq[l]]+sqr[abs(i-seq[l])] < arr[seq[l+1]]+sqr[abs(i-seq[l+1])]) l ++;
        ans[i] = std :: max(ans[i], arr[seq[l]]-arr[i]+sqr[abs(i-seq[l])]);
        while(l <= r && arr[seq[r]]+sqr[abs(i-seq[r])] < arr[i]) r --;
        seq[++ r] = i;
    }
    for(int i = N; i>=1; i--)
        printf("%d\n", ans[i]);
}

为什么是错误的呢? 上面给出的图片应该就是一个反例。
以上面的图片为例，当i到达4时，单调队列内应该有2和3两个元素。当4加入队尾时，此时4对于i=4并没有3优秀，于是3没有被弹出。当i>4时此时处于队首的2不会被紧随的3弹出，应为a2=a3,2将永远比3优。而在转移到i>4时变得比2,3都要更优的4则被挤到了队尾无法翻身。
由此可见，错误的根本原因是队列内元素随着i的增大优劣性的改变，形象地想象一下,会发现此时的单调队列中出现了一个“波谷”,单调队列无法处理这种波谷。

那么正确的做法是什么呢？
仍然用单调队列维护决策点。对每个决策点额外保存两个值lef和rig,表示从当前这个决策点转移到区间[lef, rig]是最优的。那么每次向单调队列中增加节点时,如果队尾元素转移到的它的lef比i转移到队尾的lef差，那么队尾元素必然失去了意义,直接弹出。
如果i把队列弹空了就直接插入i,否然i作为决策点的rig必然等于当前队尾的rig,lef则在区间[队尾.lef, 队尾.rig]之间。在区间内二分出i的lef值,更新队尾rig值为lef-1后在队尾插入i即可。

最后的忠告:比较两个决策点哪个更优时不能把平方根向上取整。。。被一阵狂卡。。还是我太弱了啊。。
下面贴代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <cmath>
const int MAXN = 501000;
int arr[MAXN], sqr[MAXN+500], ans[MAXN];
int lef[MAXN], rig[MAXN];
int seq[MAXN];
int N;
double calt (int a, int b) {return (double)arr[a]+sqrt(abs(a-b));}
void process () {
    int l = 0, r = -1; seq[++r] = 1; lef[r] = 2, rig[r] = N;
    for(int i = 2; i<=N; i++) {
        while(l <= r && i > rig[l]) l ++;
        lef[l] = std :: max(lef[l], i+1);
        ans[i] = std :: max(ans[i], (int)ceil(calt(seq[l], i))-arr[i]);
        if(calt(i, N) < calt(seq[r], N)) continue;
        while(l <= r && calt(seq[r], lef[r]) < calt(i, lef[r])) r--;
        if(l > r) {seq[++ r] = i, lef[r] = i+1, rig[r] = N; continue ;}
        int lb = lef[r], rb = rig[r], p = -1;
        while(lb <= rb) {
            int mid = (lb+rb)>>1;
            if(calt(seq[r], mid) <= calt(i, mid)) p = mid, rb = mid-1;
            else lb = mid+1;
        }
        rig[r] = p - 1; seq[++r] = i; lef[r] = p; rig[r] = N;
    }
}
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%d", &arr[i]);
    process();
    std :: reverse(arr+1, arr+N+1);
    std :: reverse(ans+1, ans+N+1);
    process();
    for(int i = N; i>=1; i--)
        printf("%d\n", ans[i]);
    return 0;
}