正文
[BZOJ4850][JSOI2016]灯塔(分块/决策单调性优化DP)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
第一种方法是决策单调性优化DP。
决策单调性是指，设i>j，若在某个位置x(x>i)上，决策i比决策j优，那么在x以后的位置上i都一定比j优。
根号函数是一个典型的具有决策单调性的函数，由于根号函数斜率递减，所以i决策的贡献的增长速度必定比j快。
于是使用基础的决策单调性优化即可。
注意两个问题，一是DP函数要存实数而不能存整数，因为先取整会丢失在后面的判断中需要的信息。二是记录决策作用区间的时候左端点要实时更新，即下面的p[st].l++，否则在二分时会出现错误。
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
double f[N],g[N];
int n,st,ed,h[N];
struct P{ int l,r,p; }q[N]; int Abs(int x){ return (x>) ? x : -x; }
double cal(int x,int y){ return h[x]-h[y]+sqrt(Abs(y-x)); } int find(P a,int b){
int L=a.l,R=a.r;
while (L<R){
int mid=(L+R)>>;
if (cal(a.p,mid)>=cal(b,mid)) L=mid+; else R=mid;
}
return L;
} void work(double f[]){
st=ed=; q[]=(P){,n,};
rep(i,,n){
q[st].l++; if (q[st].l>q[st].r) st++;
f[i]=cal(q[st].p,i);
if (st>ed || (cal(q[ed].p,n)<cal(i,n))){
while (st<=ed && cal(q[ed].p,q[ed].l)<cal(i,q[ed].l)) ed--;
if (st>ed) q[++ed]=(P){i,n,i};
else{
int t=find(q[ed],i); q[ed].r=t-; q[++ed]=(P){t,n,i};
}
}
}
} int main(){
scanf("%d",&n);
rep(i,,n) scanf("%d",&h[i]);
work(f); reverse(h+,h+n+);
work(g); reverse(g+,g+n+);
rep(i,,n) printf("%d\n",max((int)ceil(max(f[i],g[i])),));
return ;
}
第二种方法是分块。
这题中，对于固定的i，sqrt(i-j)只有O(sqrt(n))种取值，而每种取值的区间长度也只有O(sqrt(n))个。
预处理从每个数开始后O(sqrt(n))个数中的最大值，暴力枚举sqrt(i-j)的取值更新答案。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; const int N=,K=;
int n,ans,h[N],mx[N][]; int main(){
freopen("bzoj4850.in","r",stdin);
freopen("bzoj4850.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%d",&h[i]);
rep(i,,n){
mx[i][]=h[i];
rep(j,,min(K,n-i+)) mx[i][j]=max(mx[i][j-],h[i+j-]);
}
rep(i,,n){
ans=;
for (int pos=i,j=,nxt; pos!=; j++)
nxt=pos-,pos=max(pos-j*+,),ans=max(ans,mx[pos][nxt-pos+]-h[i]+j);
for (int pos,j=,nxt=i; nxt!=n; j++)
pos=nxt+,nxt=min(nxt+j*-,n),ans=max(ans,mx[pos][nxt-pos+]-h[i]+j);
printf("%d\n",ans);
}
return ;
}
