题意：

　　要选出一组序列，求老鼠的体重是递增的，而老鼠的速度是递减的这样的序列长度最长是多少，答案有很多种，输出一种即可。

 

坑爹：

　　用数组 cd 来记录第i只老鼠前面有多少只是符合条件的，但一开始我是让 j = i - 1 ~ 0 这样找，找到就break，但这样不行，

比如说：

重量      速度        cd数组的值

500       50                1

1000     30                2

1100     90                1

4000     30                2

这样就不对了，是要找到前面能符合条件的最大的cd值。

 

解法：

　　将num数组（存输入的值）进行排序，根据老鼠的重量进行由小到大排序，利用 数组 cd 知道最长的序列有多长，然后用了

结构体的成员step来记录当前点的老鼠比他的体重小且速度大的那个老鼠的位置。

 

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5  6 const int maxn = 10000 + 10; 7  8 struct rats 9 {10     int fat;11     int speed;12     int step;13     int count;14     friend bool operator < (rats a,rats b)15     {16         return a.fat
         
          =0; j--)48         {49             if(cd[j]>m)50             {51                 if(num[i].speed
          
           num[j].fat)52                 {53                     m=cd[j];54                     cd[i]=cd[j]+1;55                     num[i].step=j;56                 }57                 58             }59         }60         if(cd[i]==0)61         {62             num[i].step=i;63             cd[i]=1;64         }65     }66 67     int MAXN=0;68     int k=0;69     for(i=0; i
           
            MAXN)72 {73 MAXN=cd[i];74 k=i;75 }76 }77 cout<
            
             <
             
               Q;79 while(num[k].step!=k)80 {81 Q.push(num[k]);82 k=num[k].step;83 }84 cout<
              
               <