孤独一生

题目描述

下课了， Polo 来到球场，但他到了之后才发现……被放了飞机……

无事可做的他决心找点乐子，比方说……跳台阶……

球场边有 N 个台阶拍成一行，第 i 个台阶的高度是 Hi(0<Hi<=10^9)，第 0个台阶，也就是地面的高度为 0。

Polo 打算把这 N 个台阶分成两个集合 Sa,Sb（可以为空），对于一个台阶集合 S={P1,P2,…P|S|}，

其中 P1<P2<…<P|S|，他需要花费 的体力值来完成。

现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？

题解

考虑一个O(n^2)DP，我们假定$f[i][j]$表示$A$集合以$i$结尾，$B$集合以$j$结尾，$i>j$。我们画个图就可以发现$当i,j之间有空格的时候，f[i][j]=f[i-1]+abs(h[i]-h[i-1]),i>j+1$没有空格的时候我们要枚举$f[i][i-1]=min(f[i-1][k]+abs(h[i]-h[k])+abs(h[i]-h[k])$可以理解为枚举B的长度（A，B）并不绝对，只是表示一个互异关系。 那么我们可以发现前者很好转移，后者不好转移，于是我们思考后者，其实我们发现后者的dp可以单独拿出来做记$g[i]=f[i][i-1]$，则$g[i]=min(g[j]+sum[i-1]-sum[j]+abs(h[i]-h[j-1])$同样可以理解成枚举集合长度。那么我们把绝对值拿掉就好做了，考虑做一个权值树状数组，一切就显然了。

代码

#include<bits/stdc++.h> #define maxn 500005 #define INF 0x3f3f3f3f #define LL long long using namespace std; LL read(){ LL res,f=1; char c; while(!isdigit(c=getchar())) if(c=='-') f=-1; res=(c^48); while(isdigit(c=getchar())) res=(res<<3)+(res<<1)+(c^48); return res*f; } int p=1,n,h[maxn],d[maxn],rk[maxn]; LL sum[maxn],f[maxn],ans=INF; struct TR{ LL arr[maxn]; TR(){ memset(arr,0x3f,sizeof arr); } void update(int x,LL w,int f){ for(;x>0 && x<=p;x+=f*(x&-x)){ arr[x]=min(arr[x],w); } } LL query(int x,int f){ LL res=INF; for(;x>0 && x<=p;x-=f*(x&-x)){ res=min(arr[x],res); } return res; } }a,b; //a:h[j]<h[i] b:h[j]>=h[i] bool cmp(int x,int y){return h[x]<h[y];} int main(){ n=read(); for(int i=1;i<=n;i++){ h[i]=read(); d[i]=i; sum[i]=sum[i-1]+abs(h[i]-h[i-1]); } sort(d+1,d+n+1,cmp); for(int i=1;i<=n;i++) rk[d[i]]=h[d[i]]==h[d[i-1]]?p:++p; f[1]=h[1]; a.update(1,0,1); b.update(1,0,-1); ans=sum[n]; for(int i=2;i<=n;i++){ f[i]=sum[i-1]+min(a.query(rk[i],1)+h[i],b.query(rk[i],-1)-h[i]); a.update(rk[i-1],f[i]-sum[i]-h[i-1],1); b.update(rk[i-1],f[i]-sum[i]+h[i-1],-1); ans=min(ans,f[i]+sum[n]-sum[i]); } printf("%lld\n",ans); return 0; }