本文共 918 字，大约阅读时间需要 3 分钟。

题意：第一列，给出老鼠的重量，第二列，给出老鼠的速度，要证明老鼠的重量越大，速度越小，给出最多老鼠的数量，并说明第几只。

思路：先将老鼠按照重量从大到小排序，然后速度是从小到大，求最长上升子序列，学习下怎么输出最长上升子序列的路径，输出最长上升子序列路径有很多种方法，这里面是记录每个数字在最长上升子序列中的下标。因为在维护最长上升子序列数组的时候，我们会遍历到每一个元素。代码里面有样例；

//最长上升子序列输出路径/*1 7 3 5 2记录在递增序列中的下标 逆序检索1 2 2 3 21 71 31 3 51 2 5*/#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;struct node{    int w,v,a;}q[10100];bool cmp(node a,node b){    return a.w>b.w;}int main(){    int n=1;    while(scanf("%d%d",&q[n].w,&q[n].v)!=EOF)    {        q[n].a=n;n++;    }    sort(q+1,q+n+1,cmp);//    for(int i=1;i<=n;i++)//        printf("%d %d %d\n",q[i].a,q[i].w,q[i].v);    int dp[10100]={0},k=1,flag[10100]={0};    dp[1]=q[1].v;    flag[1]=1;    int len=0;    for(int i=1;i<=n;i++)    {        if(dp[k]
       
        =1;i--)// 逆序检索    {        if(k==flag[i])        {            k--;            printf("%d\n",q[i].a);        }    }    return 0;}
       
      
     
    
   

转载地址：http://fgsl.baihongyu.com/