Bzoj2216 [poi2011]lightning conductor

正经的决策单调性

Posted by yjjr's blog on January 18, 2018

Description

Output

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

Sample Input 6

5

3

2

4

2

4

Sample Output 2

3

5

3

5

4

分析

$f[i]=max\{a[j]+sqrt(i-j)\}-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;
{
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){
rep(i,1,n){
else{int t=find(que[tail],i);que[tail].r=t-1;que[++tail]=(node){t,n,i};}
}
}
}
int main()
{