[BZOJ]2216Lightning Conductor[POI2011]

题目描述

Progressive climate change has forced the Byteburg authorities to build a huge lightning conductor that would protect all the buildings within the city.

These buildings form a row along a single street, and are numbered fromto.

The heights of the buildings and the lightning conductor are non-negative integers.

Byteburg's limited funds allow construction of only a single lightning conductor.

Moreover, as you would expect, the higher it will be, the more expensive.

The lightning conductor of heightlocated on the roof of the building(of height) protects the building(of height) if the following inequality holds:

wheredenotes the absolute value of the difference betweenand.

Byteasar, the mayor of Byteburg, asks your help.

Write a program that, for every building, determines the minimum height of a lightning conductor that would protect all the buildings if it were put on top of the building.

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

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

输入输出格式

输入格式

In the first line of the standard input there is a single integer() that denotes the number of buildings in Byteburg.

Each of the followinglines holds a single integer() that denotes the height of the-th building.

输出格式

Your program should print out exactlylines to the standard output.

The-th line should give a non-negative integerdenoting the minimum height of the lightning conductor on the-th building.

输入输出样例

输入样例

输出样例

说明

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

对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j, $$ a_j \leq a_i + p - \sqrt{|i-j|}$$

思路

斜率优化DP+二分

将不等式变一下形就可以得到这个:$$ P\ge { A }{ j }+\sqrt { \left| i-j \right| } -{ A }{ i } $$
由于对任意的A都成立,那么就有$$ P=max{ { A }{ j }+\sqrt { \left| i-j \right| } -{ A }{ i }} $$这个是满足决策单调性的,假设存在 $$j>k $$且j比k更优,考虑到函数$$ f(x)=x $$为一个上凸函数,那么由于$$ i−k$$于$$i−j$$的增长速度相同,而i−k更大,所以$$f(k)=i−k$$也就增长得越快(就是下跌得更猛).所以可以用决策单调性优化.那么就可以二分决策的端点进行dp了.绝对值左右两遍dp一下就可以去掉了.

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

static const int maxn=1e6+10;
int a[maxn];
int n;
int f[maxn],g[maxn];

void half1(int l,int r,int L,int R)
{
    if(l>r || L>R)    return ;
    int mid=(l+r)>>1,pos=0;double Max=0;
    for(int i=L;i<=R && i<=mid;i++)
        if((double)a[i]+sqrt(mid-i)>=Max)
            pos=i,Max=(double)a[i]+sqrt(mid-i);
    f[mid]=a[pos]+ceil(sqrt(mid-pos));

    half1(l,mid-1,L,pos);
    half1(mid+1,r,pos,R);
}

void half2(int l,int r,int L,int R)
{
    if(l>r || L>R)    return;
    int mid=(l+r)>>1,pos=0;double Max=0;
    for(int i=R;i>=L && i>=mid;i--)
        if((double)a[i]+sqrt(i-mid)>=Max)
            pos=i,Max=(double)a[i]+sqrt(i-mid);
    g[mid]=a[pos]+ceil(sqrt(pos-mid));

    half2(l,mid-1,L,pos);
    half2(mid+1,r,pos,R);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    half1(1,n,1,n);
    half2(1,n,1,n);
    for(int i=1;i<=n;i++)
    printf("%d\n",max(f[i],g[i])-a[i]);
}

[BZOJ]Lightning Conductor