这个题意和数据范围一看就是离散化之后树状数组优化DP.给的"从左下方走上去才能拿到收益"的性质其实可以当成"必须从横纵坐标严格比某个点小的地方转移过来".1A了.~咸鱼产生了能翻身的错觉~
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100005; int f[maxn]; int x[maxn],y[maxn],v[maxn]; int seq[maxn]; int newx[maxn],newy[maxn]; bool cmpx(const int &a,const int &b){ return x[a]<x[b]; } bool cmpy(const int &a,const int &b){ if(y[a]!=y[b])return y[a]<y[b]; return x[a]>x[b]; } int c[maxn]; int gmax(int x){ int ans=0; for(;x;x-=x&(-x))ans=max(ans,c[x]); return ans; } int add(int x,int y){ for(;x<maxn;x+=x&(-x))c[x]=max(c[x],y); } int main(){ int t;scanf("%d",&t); while(t--){ memset(c,0,sizeof(c)); int n;scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d%d%d",x+i,y+i,v+i); for(int i=1;i<=n;++i)seq[i]=i; sort(seq+1,seq+n+1,cmpx); newx[seq[1]]=1; for(int i=2;i<=n;++i){ if(x[seq[i]]!=x[seq[i-1]])newx[seq[i]]=newx[seq[i-1]]+1; else newx[seq[i]]=newx[seq[i-1]]; } sort(seq+1,seq+n+1,cmpy); for(int i=1;i<=n;++i){ add(newx[seq[i]],gmax(newx[seq[i]]-1)+v[seq[i]]); } printf("%d\n",gmax(maxn-1)); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/9877537.html
