程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> FatMouses Speed

FatMouses Speed

編輯:C++入門知識

FatMouse's Speed

[cpp] 
 

[cpp] 
// File Name: hdu1160.cpp  
// Author: rudolf  
// Created Time: 2013年04月25日 星期四 14時47分25秒  
 
 #include<vector>  
 #include<list>  
 #include<map>  
 #include<set>  
 #include<deque>  
 #include<stack>  
 #include<bitset>  
 #include<algorithm>  
 #include<functional>  
 #include<numeric>  
 #include<utility>  
 #include<sstream>  
 #include<iostream>  
 #include<iomanip>  
 #include<cstdio>  
 #include<cmath>  
 #include<cstdlib>  
 #include<cstring>  
 #include<ctime>  
 #include<string.h>  
 using namespace std; 
 const int maxn = 1005; 
 struct node 
 { 
     int w,v,num; 
 }mouse[ maxn ]; 
 int dp[ maxn ]; 
 int path[ maxn ]; 
 int cmp( node a1,node a2 ) 
 { 
     if( a1.w!=a2.w )  
         return a1.w<a2.w; 
     else  
         return a1.v>a2.v; 
 } 
 int main() 
 { 
     int cnt=0; 
     while( scanf("%d%d",&mouse[ cnt ].w,&mouse[ cnt ].v)!=EOF ) 
     { 
         mouse[ cnt ].num=cnt+1; 
         path[ cnt ]=-1; 
         cnt++; 
     } 
     sort( mouse,mouse+cnt,cmp ); 
     int max_dp,max_num; 
     max_dp=max_num=0; 
     dp[ 0 ]=1; 
     for( int i=1;i<cnt;i++ ) 
     { 
         int my_max=0; 
         for( int j=0;j<i;j++ ) 
         { 
             if( mouse[ j ].v>mouse[ i ].v && my_max<dp[ j ] && mouse[ j ].w!=mouse[ i ].w ) 
             { 
                 my_max=dp[ j ]; 
                 path[ i ]=j; 
             } 
         } 
         dp[ i ]=my_max+1; 
         if( max_dp<dp[ i ] ) 
    { 
             max_dp=dp[ i ]; 
             max_num=i; 
         } 
     } 
     stack<int>s; 
     s.push( mouse[max_num].num ); 
     while( path[max_num]!=-1 ) 
     { 
         s.push(mouse[path[max_num]].num); 
         max_num=path[max_num]; 
     } 
     printf("%d\n",s.size()); 
     while( !s.empty() )  
     { 
         printf("%d\n",s.top() ); 
         s.pop(); 
     } 
     return 0; 
 } 

// File Name: hdu1160.cpp
// Author: rudolf
// Created Time: 2013年04月25日 星期四 14時47分25秒

 #include<vector>
 #include<list>
 #include<map>
 #include<set>
 #include<deque>
 #include<stack>
 #include<bitset>
 #include<algorithm>
 #include<functional>
 #include<numeric>
 #include<utility>
 #include<sstream>
 #include<iostream>
 #include<iomanip>
 #include<cstdio>
 #include<cmath>
 #include<cstdlib>
 #include<cstring>
 #include<ctime>
 #include<string.h>
 using namespace std;
 const int maxn = 1005;
 struct node
 {
     int w,v,num;
 }mouse[ maxn ];
 int dp[ maxn ];
 int path[ maxn ];
 int cmp( node a1,node a2 )
 {
     if( a1.w!=a2.w )
   return a1.w<a2.w;
     else
   return a1.v>a2.v;
 }
 int main()
 {
     int cnt=0;
     while( scanf("%d%d",&mouse[ cnt ].w,&mouse[ cnt ].v)!=EOF )
  {
         mouse[ cnt ].num=cnt+1;
         path[ cnt ]=-1;
         cnt++;
     }
     sort( mouse,mouse+cnt,cmp );
     int max_dp,max_num;
     max_dp=max_num=0;
     dp[ 0 ]=1;
     for( int i=1;i<cnt;i++ )
  {
         int my_max=0;
         for( int j=0;j<i;j++ )
   {
             if( mouse[ j ].v>mouse[ i ].v && my_max<dp[ j ] && mouse[ j ].w!=mouse[ i ].w )
    {
                 my_max=dp[ j ];
                 path[ i ]=j;
             }
         }
         dp[ i ]=my_max+1;
         if( max_dp<dp[ i ] )
 {
             max_dp=dp[ i ];
             max_num=i;
         }
     }
     stack<int>s;
     s.push( mouse[max_num].num );
     while( path[max_num]!=-1 )
  {
         s.push(mouse[path[max_num]].num);
         max_num=path[max_num];
     }
     printf("%d\n",s.size());
     while( !s.empty() )
  {
         printf("%d\n",s.top() );
         s.pop();
     }
     return 0;
 }


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved