[BZOJ2216]&&[Poi2011] Lightning Conductor

2014-12-01
竞赛题解 / 动态规划
BZOJPOI

描述 Description

已知一个长度为 n 的序列 a1,a2,…,an。

对于每个 1<=i<=n，找到最小的非负整数 p 满足 对于任意的 j, aj < = ai + p - sqrt(abs(i-j))

输入格式 InputFormat

第一行 n，(1<=n<=500000)

下面每行一个整数，其中第 i 行是 ai。(0<=ai<=1000000000)

输出格式 OutputFormat

n 行，第 i 行表示对于 i，得到的 p

样例输入 SampleInput

6
5
3
2
4
2
4

样例输出 SampleOutput

2
3
5
3
5
4

BZOJ 2216

$a_ja_i + p - $ 得 $ a_j + - ai p$, 于是对于每个 i 要最大化 \(a_j + \sqrt{|i-j|}\)

决策单调性优化。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=500005;
int i,j,t,n,m,l,r,k,z,y,x;
struct data
{
    int l,r,id;
    data() {}
    data(int id,int l,int r): id(id),l(l),r(r) {}
}q[maxn];
int a[maxn];
double f[maxn],g[maxn];
int head,tail;
inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline double calc(int x,int y)
{
    return a[y]+sqrt(abs(x-y))-a[x];
}
inline int find(int l,int r,int x,int y)
{
    int mid;
    while (l<r)
    {
        mid=(l+r)>>1;
        if (calc(mid,x)<calc(mid,y)) l=mid+1;
        else r=mid;
    }
    return l;
}
inline void dp(double *f)
{
    int i,j,t;
    head=1;tail=0;
    for (i=1;i<=n;i++) 
    {
        if (head<=tail && ++q[head].l>q[head].r) head++;
        if (head>tail || calc(n,i)>calc(n,q[tail].id))
        {
            while (head<=tail && calc(q[tail].l,i)>calc(q[tail].l,q[tail].id)) tail--;
            if (head>tail) q[++tail]=data(i,i,n);
            else
            {
                t=find(q[tail].l,q[tail].r,i,q[tail].id);
                q[tail].r=t-1;
                q[++tail]=data(i,t,n);
            }
        }
        f[i]=calc(i,q[head].id);
    }
}
int main()
{
    read(n);
    for (i=1;i<=n;i++) read(a[i]);
    dp(f);
    reverse(a+1,a+n+1);
    dp(g);
    reverse(g+1,g+n+1);
    for (i=1;i<=n;i++) printf("%d\n",max(0,(int)ceil(max(f[i],g[i]))));
    return 0;
}