本想用暴力法先试试的，案例和自己找的数据都过掉了，但是始终wa，本来期待的是tle，结果始终wa。所以也就懒的管了，直接用dp来做了。主要是因为最近在刷暴力法和dp这两个专题，所以才想好好利用一下这道题。如果有哪位发现了我的第一个程序的错误，还望告知。

暴力法（此程序不知道为何wa）

1 #include"iostream" 2 #include"stdio.h" 3 #include"string.h" 4 #include"cmath" 5 #include"algorithm" 6 #define mx 1005 7 using namespace std; 8 int cur[mx]; 9 int end1[mx];10 struct node11 {12     int v; 13 int w; 14 int num; 15 }mice[mx]; 16 node temp; 17 bool cmp(const node a,const node b) 18 { 19 if(a.w!=b.w) return a.w
     
      b.v; 21 } 22 int main() 23 { 24 int i,j,k,sum=0; 25 // while(1){ 26 while(scanf("%d%d",&mice[sum].w,&mice[sum].v)==2) {mice[sum].num=sum+1;sum++;} 27 sort(mice,mice+sum,cmp); 28 int maxsum=0; 29 for(i=0;i
      
       mice[j].v&&temp.w!=mice[j].w) 37  { 38 cur[++k]=mice[j].num; 39 temp=mice[j]; 40  } 41  } 42 if(k+1>maxsum) {memcpy(end1,cur,sizeof(cur));maxsum=k+1;} 43  } 44 cout<
       
        <
       
      
     

接下来是ac掉的简单dp：这道题的思路其实很简单，是一个典型的dp问题——最长上升子序列问题。状态转移方程为

if(dp[j]+1>dp[i])dp[i]=dp[j]+1.用一个pre数组来记录每一个i对应的前一个j，用于后面回溯，将路径存入path中。maxlen用于记录最长上升子序列的长度。maxindex用于记录最长上升子序列对应的最大的i。

1 #include"iostream" 2 #include"stdio.h" 3 #include"cmath" 4 #include"algorithm" 5 #include"string.h" 6 #define mx 1005 7 using namespace std; 8 struct node 9 {10     int w,v,index;11 }mouse[mx];12 int dp[mx];//记录每个以第i个数据结尾的符合要求的子列长度13 int pre[mx];//记录i对应的上一个数据14 int path[mx];//存放最终结果的下标15 int maxlen;//最长序列的长度16 int maxindex;//最长序列的最后一个数下标17 bool cmp(const node a,const node b)18 {19     if(a.w!=b.w) return a.w
     
      b.v;21 }22 int main()23 {24     int i,j,k=1;25     while(scanf("%d%d",&mouse[k].w,&mouse[k].v)==2)26     {27         dp[k]=1;28         pre[k]=0;29         mouse[k].index=k;//存放未排序前的序列号，因为结果需要输出的是这个序列号30         k++;31     }32     sort(mouse+1,mouse+k,cmp);//以重量从小到大为第一要求，速度从大到小为第二要求排序33     maxlen=0;34     for(i=1;i
      
       mouse[j].w&&mouse[i].v
       
        dp[i]) 39             {40                 dp[i]=dp[j]+1;41                 pre[i]=j;//一第i个数据位末尾数据的前一个数据的小标是j，用于回溯42                 if(dp[i]>maxlen)//更新maxlen和maxindex43                 {44                     maxlen=dp[i];45                     maxindex=i;46                 }47             }48         }49     }50     i=0;51     while(maxindex) //回溯找到原始下标的序列52     {53         path[i++]=maxindex;54         maxindex=pre[maxindex];55     }56     cout<
        <