N个连续的盒子，每个盒子有高度h和价值v，，选择任意一点进入，且从任意一点出来，进入后只能从左向右走，且每次走到的盒子高度必须更高，可以跳过低的盒子
状态转移方程：dp[i]=max(dp[j])+v[i], (0<=j<i && h[i]>h[j])
用线段树优化，寻找 j<i 的最大dp值，需要先对h进行离散化
#include "stdio.h"#include "string.h"#include "queue"#include "algorithm"using namespace std;struct Mark{int h,v,id;}b[100100],mark[100100];struct Data{int l,r,v;}data[400010];bool cmp(Mark a,Mark b){return a.h<b.h;}int Max(int a,int b){if (a<b) return b;else return a;}void build(int l,int r,int k){int mid;data[k].l=l;data[k].r=r;data[k].v=0;if (l==r) return ;mid=(l+r)/2;build(l,mid,k*2);build(mid+1,r,k*2+1);}void updata(int h,int v,int k){int mid;if (data[k].l==h && data[k].r==h){data[k].v=Max(v,data[k].v);return;}mid=(data[k].l+data[k].r)/2;if (h<=mid) updata(h,v,k*2);else updata(h,v,k*2+1);data[k].v=Max(data[k*2].v,data[k*2+1].v);}int query(int l,int r,int k){int mid;if (data[k].l==l && data[k].r==r)return data[k].v;mid=(data[k].l+data[k].r)/2;if (r<=mid) return query(l,r,k*2);elseif (l>mid) return query(l,r,k*2+1);elsereturn Max(query(l,mid,k*2),query(mid+1,r,k*2+1));}int main(){int i,h,temp,ans,n;while (scanf("%d",&n)!=EOF){for (i=1;i<=n;i++){scanf("%d%d",&b[i].h,&b[i].v);b[i].id=i;}sort(b+1,b+1+n,cmp);h=1;mark[b[1].id].h=1;mark[b[1].id].v=b[1].v;for (i=2;i<=n;i++){if(b[i].h!=b[i-1].h) h++;mark[b[i].id].h=h;mark[b[i].id].v=b[i].v;}build(0,h,1);updata(mark[1].h,mark[1].v,1);ans=mark[1].v;for (i=2;i<=n;i++){temp=query(0,mark[i].h-1,1)+mark[i].v;ans=Max(ans,temp);updata(mark[i].h,temp,1);}printf("%d\n",ans);}return 0;}
好好的管教你自己，不要管别人。
