1108 fatmouse's speed.txt

浙江大学ACM练习题 1108 提交通过原代码

#include <stdio.h>
#include <string.h>
int main()
{
     struct seta
     {
            int w;
            int s;
   int hou;
   int num;
     };
     
     seta a[11100];
     seta tp;
     int tt,tt2,s,w;
     int maxn;
     int n;
     int i,j;
     int b[11100];
     i=0;
     while (scanf("%d%d\n",&w,&s)!=EOF)
     {
           i++;
           a[i].w=w;
           a[i].s=s;
     a[i].num=i;
     }
     
     n=i;
     for (i=1;i<=n-1;i++)
     for (j=i+1;j<=n;j++)
     {
                
         
         if (a[i].w>a[j].w)
         {
             tp=a[i];
             a[i]=a[j];
             a[j]=tp;
         }              
         if (a[i].w==a[j].w)
         {
                           if (a[i].s<a[j].s)
                           {
                                             tp=a[i];
                                             a[i]=a[j];
                                             a[j]=tp;
                           }       
         }
     }
     memset(b,0,sizeof(b));
     a[n+1].s=-1;
     for (i=n;i>=1;i--)
     {
         maxn=0;        
         for (j=i+1;j<=n+1;j++)
         {
                if ((a[j].s<a[i].s)&&(b[j]+1>=maxn)&&(a[i].w!=a[j].w)) 
                {
                      maxn=b[j]+1;
                      tt=j;
    }
         }
   a[i].hou=tt;
         b[i]=maxn;
     }
     maxn=0;
     for (i=1;i<=n;i++)
     {
         if (b[i]>=maxn)
         {maxn=b[i];
    tt2=i;
   }
         

     }
     printf("%d\n",maxn);
     do
  {
        printf("%d\n",a[tt2].num);
  tt2=a[tt2].hou;
  }
  while (tt2!=n+1);
  return 0;
    
}