题意：给定一些小猫的属性：体重和速度。然后求某些猫顺序的排列，使得体重上升，速度下降，这样的排列尽量长。
DP+排序
即：最长下降子序列
View Code
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<stack> 5 using namespace std; 6 const int maxn = 1005; 7 struct node{ 8 int w,v,num; 9 }mouse[ maxn ]; 10 int dp[ maxn ]; 11 int path[ maxn ]; 12 int cmp( node a1,node a2 ){ 13 if( a1.w!=a2.w ) return a1.w<a2.w; 14 else return a1.v>a2.v; 15 } 16 int main(){ 17 int cnt=0; 18 while( scanf("%d%d",&mouse[ cnt ].w,&mouse[ cnt ].v)!=EOF ){ 19 mouse[ cnt ].num=cnt+1; 20 path[ cnt ]=-1; 21 cnt++; 22 } 23 sort( mouse,mouse+cnt,cmp ); 24 int max_dp,max_num; 25 max_dp=max_num=0; 26 dp[ 0 ]=1;//dp[ 0 ]=mouse[ 0 ].v; 27 for( int i=1;i<cnt;i++ ){ 28 int my_max=0; 29 for( int j=0;j<i;j++ ){ 30 if( mouse[ j ].v>mouse[ i ].v && my_max<dp[ j ] && mouse[ j ].w!=mouse[ i ].w ){ 31 my_max=dp[ j ]; 32 path[ i ]=j; 33 } 34 } 35 dp[ i ]=my_max+1;//dp[ i ]=my_max+mouse[ i ].v; 36 if( max_dp<dp[ i ] ){ 37 max_dp=dp[ i ]; 38 max_num=i; 39 }//find the longest, dp[ max_num ] is the ANS 40 } 41 stack<int>s; 42 s.push( mouse[max_num].num ); 43 while( path[max_num]!=-1 ){ 44 s.push(mouse[path[max_num]].num); 45 max_num=path[max_num]; 46 } 47 printf("%d\n",s.size()); 48 while( !s.empty() ) { 49 printf("%d\n",s.top() ); 50 s.pop(); 51 } 52 return 0; 53 } 54