Bzoj2216 [poi2011]lightning conductor

正经的决策单调性


本文总阅读量
Posted by yjjr's blog on January 18, 2018

标签:决策单调性DP,单调队列,二分

题目

题目传送门

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 6

5

3

2

4

2

4

Sample Output 2

3

5

3

5

4

分析

先普通DP,f[i]就是对应的P

\[f[i]=max\{a[j]+sqrt(abs(i-j))\}-a[i]\]

显然,这样做法时间复杂度是O(n^2),因为这题是1D1D(就是存在n种状态,每种状态存在n种转移)

把绝对值去掉

\(f[i]=max\{a[j]+sqrt(i-j)\}-a[i]\ (i>=j)\) \(f[i]=max\{a[j]+sqrt(j-i)\}-a[i]\ (i<j)\)

这两个式子很显然决策单调,然后可以用单调队列优化+二分

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=5e5+6;
int n,a[maxn];
double f[maxn],g[maxn];
struct node{int l,r,p;}que[maxn];
double cal(int j,int i){return a[j]+sqrt(abs(i-j))-a[i];}
int find(node t,int x){
	int l=t.l,r=t.r,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(cal(t.p,mid)>cal(x,mid))l=mid+1;else r=mid-1;
	}
	return l;
}
void dp(double *F){
	int head=1,tail=0;
	rep(i,1,n){
		que[head].l++;
		if(head<=tail&&que[head].r<que[head].l)head++;
		if(head>tail||cal(i,n)>cal(que[tail].p,n)){
			while(head<=tail&&cal(que[tail].p,que[tail].l)<cal(i,que[tail].l))tail--;
			if(head>tail)que[++tail]=(node){i,n,i};
			else{int t=find(que[tail],i);que[tail].r=t-1;que[++tail]=(node){t,n,i};}
		}
		F[i]=cal(que[head].p,i);
	}
}
int main()
{
	n=read();
	rep(i,1,n)a[i]=read();
	dp(f);
	rep(i,1,n/2)swap(a[i],a[n-i+1]);
	dp(g);
	rep(i,1,n)printf("%d\n",max(0,(int)ceil(max(f[i],g[n-i+1]))));
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr