FatMouse‘s Speed（dp模版2 最长上升子序列

题源

这是一题最长上升子序列的变种，首先要满足两个条件，体重递增，速度递减的子序列
体重递增采用结构体排序
速度递减，采用dp状态转移，记录路径采用记录前驱的方式后reverse可以满足

#include<bits/stdc++.h>usingnamespacestd;constintN=1100;structnode{intid,wgt,spd;}arr[N];intdp[N],endix=0;intansVec[N];boolcmp(node a,node b){if(a.wgt==b.wgt){returna.spd>b.spd;}returna.wgt<b.wgt;//要注意b是主体}intmain(){inta,b,tot=0,ans=1;while(cin>>a>>b){tot++;arr[tot].id=tot;arr[tot].wgt=a;arr[tot].spd=b;}sort(arr+1,arr+1+tot,cmp);for(inti=1;i<=tot;i++){dp[i]=1;for(intj=1;j<i;j++){if(arr[i].spd<arr[j].spd&&arr[i].wgt!=arr[j].wgt){if(dp[j]+1>dp[i]){ansVec[i]=j;//记录当前结点的最长子序列的前驱}dp[i]=max(dp[i],dp[j]+1);}//ans = max(ans,dp[i]);if(ans<dp[i]){endix=i;ans=max(ans,dp[i]);}}}cout<<ans<<"\n";vector<int>res;res.push_back(arr[endix].id);for(inti=endix;ansVec[i]!=0;){//cout<<i<<" "<<ansVec[i]<<"\n";res.push_back(arr[ansVec[i]].id);i=ansVec[i];}reverse(res.begin(),res.end());for(autoit:res){cout<<it<<"\n";}return0;}