1744：跳台阶
时间限制: 1000 ms 内存限制: 131072 KB
【题目描述】
球场边有N个台阶排成一行，第i个台阶的高度是Hi(0<Hi≤109)，第0个台阶，也就是地面的高度为0。
Polo打算把这N个台阶分成两个集合Sa,Sb（可以为空），对于一个台阶集合S={P1,P2,...，P|S|}，其中P1<P2<...<P|S|，他需要花费
(sum_{1}^{s} left |Hp[i]-Hp[i-1]
ight |)
的体力值来完成。
现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？
【输入】
第一行一个数N。
第二行N个整数Hi。
【输出】
一行一个整数，表示最小的总体力值。
【输入样例】
3
1 3 1
【输出样例】
4
【提示】
【数据规模和约定】
对于10%的数据N≤20。
对于20%的数据N≤100。
对于50%的数据N≤5000。
对于100%的数据1≤N≤500000。
【题解】
动态规划。
发现本次放组只与两组的最后一阶有关，定义f[i][j]表示两组最后一个分别放的是i,j的最小体力，默认i>j
当i>j+1时，则i必定是放在i-1上，f[i][j]=f[i-1][j]+suan(i-1,i);
当i=j+1时，则f[i][j]可以从f[i-1][k] (k in [1,i-1])转移。
发现下面的转移是O(n)的，期望得分50。
需要优化。
发现任意一个f[i][j]（i>j+1）必是从f[j+1][j]处转移得到（一直放在第一个集合）。所以只需求出所有f[i-1][j]。
定义sum[i]表示从suan(1,2)+suan(2,3)+……+suan(i-1,i)。
f[i][i-1]=min(f[k][k-1]+sum[i-1]-sum[k]+suan(k-1,i))。
设g[i]=f[i][i-1]，可以将suan里分类讨论分别求出-sum[k]+g[k]+h[k]，和-sum[k]+g[k]-h[k] 按h值压入树状数组内维护前缀最小值即可快速求出从哪儿转移。
代码如下：
#include<bits/stdc++.h> #define int long long using namespace std; const int N=5e5+5; map <int,int> dui; int n,cnt=1,ls[N],a[N]; int g[N],sum[N],sh1[N],sh2[N],ans; inline int read() { char c=getchar(); int x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return x; } inline int lowbit(int x) { return x& (-x); } inline void update1(int x,int y) { for(register int i=x;i<=cnt+1;i+=lowbit(i)) sh1[i]=min(sh1[i],y); } inline void update2(int x,int y) { for(register int i=x;i<=cnt+1;i+=lowbit(i)) sh2[i]=min(sh2[i],y); } inline int query1(int x) { int daan=100000000000000; for(register int i=x;i;i-=lowbit(i)) daan=min(daan,sh1[i]); return daan; } inline int query2(int x) { int daan=1000000000000; for(register int i=x;i;i-=lowbit(i)) daan=min(daan,sh2[i]); return daan; } signed main() { n=read(); for(register int i=1;i<=n;i++) { a[i]=read(); sum[i]=sum[i-1]+abs(a[i]-a[i-1]); ls[i]=a[i]; } sort(ls+1,ls+n+1); for(register int i=1;i<=n;i++) { if(ls[i]!=ls[i-1]) dui[ls[i]]=++cnt; } memset(sh1,63,sizeof(sh1)); memset(sh2,63,sizeof(sh2)); g[1]=a[1];ans=sum[n]; update1(1,0); update2(cnt,0); for(register int i=2;i<=n;i++) { int hu1=query1(dui[a[i]]); int hu2=query2(cnt-dui[a[i]]+1); hu1+=a[i];hu2-=a[i]; g[i]=min(hu1,hu2)+sum[i-1]; ans=min(ans,g[i]+sum[n]-sum[i]); update1(dui[a[i-1]],g[i]-sum[i]-a[i-1]); update2(cnt-dui[a[i-1]]+1,g[i]-sum[i]+a[i-1]); } cout<<ans; }