[bzoj 2216] [Poi2011] Lightning Conductor

Description

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

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

Input

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

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

Output

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

Sample Input

Sample Output

将不等式变一下形就可以得到这个:

\[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\left( x \right) =\sqrt { x } $ 为一个上凸函数,那么由于 $ i-k $ 于 $ i-j $ 的增长速度相同,而 $i-k$ 更大,所以$ f\left( k \right) =\sqrt { i-k } $也就增长得越快(就是下跌得更猛).所以可以用决策单调性优化.(即k永世不得翻身).那么就可以二分决策的端点进行dp了.绝对值左右两遍dp一下就可以去掉了.

#include <cstdio>

#include <cmath>

#include <algorithm>

using std :: max;

using std :: sqrt;

using std :: ceil;

static const int maxm = 1e6 + 10;

int f[maxm],g[maxm],A[maxm];

int n;

void solve1(int l,int r,int L,int R){

	if(l > r || L > R) return;

	int pos = 0,mid = (l + r) >> 1; double mx = 0;

	for(int i = L;i <= R && i <= mid;i++)

		if((double) A[i] + sqrt(mid - i) >= mx)

			pos = i,mx = (double) A[i] + sqrt(mid - i);

	f[mid] = A[pos] + ceil(sqrt(mid - pos));

	solve1(l,mid - 1,L,pos);

	solve1(mid + 1,r,pos,R);

}

void solve2(int l,int r,int L,int R){

	if(l > r || L > R) return;

	int pos = 0,mid = (l + r) >> 1; double mx = 0;

	for(int i = R;i >= L && i >= mid;i--)

		if((double) A[i] + sqrt(i - mid) >= mx)

			pos = i,mx = (double) A[i] + sqrt(i - mid);

	g[mid] = A[pos] + ceil(sqrt(pos - mid));

	solve2(l,mid - 1,L,pos);

	solve2(mid + 1,r,pos,R);

}

int main(){

	scanf("%d",&n);

	for(int i = 1;i <= n;i++)scanf("%d",&A[i]);

	solve1(1,n,1,n);solve2(1,n,1,n);

	for(int i = 1;i <= n;i++)printf("%d\n",max(f[i],g[i])-A[i]);

	return 0;

}

传送门(权限题,非bzoj)

巴特西

[bzoj 2216] [Poi2011] Lightning Conductor

[bzoj 2216] [Poi2011] Lightning Conductor

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章