解析: 按照速度从大到小排序，然后根据体重跑最长上升子序列。 在状态发生转移时，记录当前状态x由状态y转移过来 最后倒着遍历记录的数组，即路径
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int pre[N]; struct node { int x,y,id; bool operator < (const node &W){ return y>W.y; } }a[N]; int f[N]; int cnt,u,v; int main() { while(~scanf("%d %d",&u,&v)) { a[++cnt]={u,v,cnt}; } sort(a+1,a+1+cnt); int pos=0; int mx=0; for(int i=1;i<=cnt;i++) { f[i]=1; for(int j=1;j<i;j++) { if(a[j].x<a[i].x) { if(f[j]+1>f[i]) { f[i]=f[j]+1; pre[i]=j; if(f[i]>mx) { mx=f[i]; pos=i; } } } } } vector<int> v; int t=pos; while(t!=0) { v.push_back(t); t=pre[t]; } printf("%d\n",v.size()); reverse(v.begin(),v.end()); for(auto x:v){ printf("%d\n",a[x].id); } }