FatMouse's Speed

杭电1160
View Code
 1 //杭电1160
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #define N 1005
 5 int b[N],c[N],d[N][N];
 6 struct mouse
 7 {
 8     int w,v;
 9     int id;
10 }a[1001];
11 int cmp(const void *a,const void *b)
12 {
13     struct mouse *x,*y;
14     x=(struct mouse *)a;
15     y=(struct mouse *)b;
16     if(x->v!=y->v)
17         return x->v<y->v?1:-1;
18     else
19         return x->w>y->w?1:-1;
20 }
21 
22 
23 int main()
24 {
25     int i=0,j,k;
26     int p,t,l,h;
27     int m,n;
28     while(scanf("%d%d",&m,&n)!=-1)
29     {
30         a[i].w=m;
31         a[i].v=n;
32         a[i].id=i;
33          i++;
34          
35     }
36     k=i;
37         qsort(a,k,sizeof(a[0]),cmp);
38        int max1;
39         c[0]=1;d[0][0]=a[0].id;
40         for(i=1;i<k;i++)
41         {    p=0;t=0;b[0]=1;
42             for(j=0;j<i;j++)
43             {
44                 if(a[i].w>a[j].w)
45                 {
46                     b[p++]=c[j]+1;
47                 
48                 }
49             }
50             max1=b[0];
51             for(l=0;l<p;l++)
52             {
53                 if(max1<b[l])
54                     max1=b[l];
55             }
56             c[i]=max1;
57 
58         }
59         int max2=c[0];    
60         for(i=0;i<k;i++)
61         {
62             if(max2<c[i])
63             {
64             max2=c[i];
65         
66             h=i;
67             }
68         }
69         int y,x;
70         y=h;x=max2;
71         printf("%d\n",max2);//输出最长子序列
72         d[h][0]=a[h].id;t=1;
73         for(i=h-1;i>=0;i--)
74         {
75             if((a[y].w>a[i].w)&&(c[i]==x-1))
76             {
77                 d[h][t++]=a[i].id;
78                 x=x-1;
79                 y=i;
80                 
81             }
82         }
83         for(i=max2-1;i>=0;i--)
84 
85         printf("%d\n",d[h][i]+1);
86         return 0;
87 }
88