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

题源这是一题最长上升子序列的变种首先要满足两个条件体重递增速度递减的子序列体重递增采用结构体排序速度递减采用dp状态转移记录路径采用记录前驱的方式后reverse可以满足#includebits/stdc.husingnamespacestd;constintN1100;structnode{intid,wgt,spd;}arr[N];intdp[N],endix0;intansVec[N];boolcmp(node a,node b){if(a.wgtb.wgt){returna.spdb.spd;}returna.wgtb.wgt;//要注意b是主体}intmain(){inta,b,tot0,ans1;while(cinab){tot;arr[tot].idtot;arr[tot].wgta;arr[tot].spdb;}sort(arr1,arr1tot,cmp);for(inti1;itot;i){dp[i]1;for(intj1;ji;j){if(arr[i].spdarr[j].spdarr[i].wgt!arr[j].wgt){if(dp[j]1dp[i]){ansVec[i]j;//记录当前结点的最长子序列的前驱}dp[i]max(dp[i],dp[j]1);}//ans max(ans,dp[i]);if(ansdp[i]){endixi;ansmax(ans,dp[i]);}}}coutans\n;vectorintres;res.push_back(arr[endix].id);for(intiendix;ansVec[i]!0;){//couti ansVec[i]\n;res.push_back(arr[ansVec[i]].id);iansVec[i];}reverse(res.begin(),res.end());for(autoit:res){coutit\n;}return0;}