题不算难，记录路径的时候有点麻烦，需要去判断在相等的时候不用更新，然后搜回去就行了。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 struct ele 6 { 7     int w; 8     int s; 9     int num;10 } el[1050];11 int cmp(ele a,ele b)12 {13     return a.w
        
         el[k].s)30             d[j+1][k]=max(d[j][j]+1,d[j][k]);31             else d[j+1][k]=d[j][k];32             if(d[j+1][k]==d[j][k]) s[j+1][k]=s[j][k];33             else s[j+1][k]=j;34         }35 36     }37         int maxd=0,t;38         for(j=1;j
         
          =maxd)40         {41             maxd=d[j][j];42             t=j;43         }44         if(maxd>0)45         {46             printf("%d\n",maxd+1);47             way[maxd]=el[t].num;48             for(j=maxd-1;j>=0;j--)49             {50                 way[j]=el[s[t][t]].num;51                 t=s[t][t];52             }53             for(int k=0;k<=maxd;k++)54             {55                 printf("%d\n",way[k]);56             }57         }58     return 0;59 }