p的思路不一定要到最后去找到ans；也可以设置成在中间找到ans；比如J - FatMouse's Speed 这个题，如果要是让dp[n]成为最终答案的话，即到了i，最差的情况也是dp[i-1]，就很难去保存路径，但是如果换一个思路，让dp[i]必须去参与，如果无法与前面的结合，那么就新开一个。

　　最后路径是保存的逆序的，那么开一个stack就可以解决。

 

1 //显然这个题是要维护两个变量的最长上升子序列  2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 9 using namespace std;10 //ifstream fin("a.txt");11 struct node{12 int weight,speed,num;13 }a[10005];14 bool cmp(node a,node b)15 {16 if(a.weight==b.weight)17 return a.speed>b.speed;18 else return a.weight
           
            >x>>y)28 {29 a[i].weight=x;a[i].speed=y,a[i].num=i;i++; 30 }31 sort(a+1,a+i,cmp);32 dp[1].cnt=1;33 for(int j=2;j<=i-1;j++)34 {35 dp[j].cnt=1; 36 for(int k=j-1;k>=1;k--)37 {38 if(a[j].speed
            
             a[k].weight)39 {40 if(dp[j].cnt
             

s;63 s.push(a[m].num);ans--;64 while(ans--)65 {66 s.push(a[dp[m].pre].num);67 m=dp[m].pre;68 }69 while(!s.empty())70 {71 cout << s.top()<