题意：
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.
要求输出哪些FatMouse被选中了，按顺序输出。
思路：
最长不下降子序列，且要记录路径。
看代码
代码：
struct node{
int weight, speed, index;
}
mice[10005];
int dp[10005];
int path[10005];
int finalPath[10005];
bool cmp(node a,node b){
if(a.weight==b.weight)
return a.speed>b.speed;
return a.weight<b.weight;
}
int main(){
int cn=0;
int t1,t2;
while(scanf("%d%d",&t1,&t2)!=EOF){
++cn;
mice[cn].weight=t1;
mice[cn].speed=t2;
mice[cn].index=cn;
}
sort(mice+1,mice+1+cn,cmp);
rep(i,1,cn){
dp[i]=1;
path[i]=i;
}
rep(i,2,cn){
int temp=0;
int tempPos=i;
rep(j,1,i-1) if(mice[j].weight<mice[i].weight && mice[j].speed>mice[i].speed){
if(dp[j]>temp){
temp=dp[j];
tempPos=j;
}
}
dp[i]=temp+1;
path[i]=tempPos;
}
int ans=-1;
int ansPos=-1;
rep(i,1,cn){
if(dp[i]>ans){
ans=dp[i];
ansPos=i;
}
}
printf("%d\n",ans);
int cn2=0;
while(path[ansPos]!=ansPos){
finalPath[++cn2]=mice[ansPos].index;
ansPos = path[ansPos];
}
printf("%d\n",mice[ansPos].index);
rep2(i,cn2,1) printf("%d\n",finalPath[i]);
return 0;
}