hdu1160 参考答案

   1 {{{
   2 #!cplusplus
   3 /*
   4 zju1108,hdu1160 FatMouse's Speed:严格递增子列
   5 ymc 2008/10/10
   6 题目大意：
   7 给定n只老鼠，每只老鼠有体重和速度，求老鼠的一个最长序列，
   8 使得体重严格递增，速度严格递减。给出这个序列的长度，并且输出这个序列中
   9 的每只老鼠在输入中的序号。
  10 分析与解题思路：
  11 先对所有老鼠排序，第一个关键字体重从小到大，第二关键字速度从大到小。
  12 然后求这个序列中的最长严格递增子序列。
  13 算法参考：严格递增子序列
  14 b[i]记录以i只老鼠作为结尾的最长合法序列的长度，则有状态转移方程
  15 b[i]=max{b[j]+1},0<=j<i,并且第j只老鼠可以排在第i只老鼠前面。
  16 */
  17 #include <iostream>
  18 #include <algorithm>
  19 using namespace std;
  20 const int N=1010;
  21 struct Mice
  22 {
  23    int w; //体重
  24    int s; //速度
  25    int id;//因为输出需要序号，这里记录序号
  26 };
  27 int n;
  28 Mice a[N];
  29 int b[N]; //以i只老鼠作为结尾的最长合法序列的长度
  30 int c[N];//以第i只老鼠作为结尾的最长合法序列的倒数第二只老鼠的序号
  31 int len;
  32 int d[N];
  33 bool Cmp(const Mice &b,const Mice &c)
  34 {
  35      return (b.w<c.w||b.w==c.w&&b.s>c.s);
  36 }
  37 void DP()
  38 {
  39      sort(a,a+n,Cmp);
  40      b[0]=1;
  41      c[0]=-1;     
  42      for(int i=1;i<n;i++) //
  43      {
  44          b[i]=1;
  45          c[i]=-1;
  46          for(int j=0;j<i;j++)
  47          {
  48             if(a[j].w<a[i].w && a[j].s>a[i].s&&b[j]+1>b[i])
  49             {
  50               b[i]=b[j]+1;
  51               c[i]=j;
  52             }
  53          }
  54  
  55      }
  56    int max=n-1;
  57    for(int j=n-1;j>=0;j--)//最长的序列长度，以及最后一直老鼠的序号
  58      if(b[j]>b[max]) max=j; 
  59    
  60    int j=max;
  61    len=b[max];
  62    while(c[j]!=-1) //输出序列，写的有点乱。
  63    {
  64       d[--len]=a[j].id;
  65       j=c[j];
  66    }
  67    d[0]=a[j].id;
  68    cout<<b[max]<<endl;
  69    for(int i=0;i<b[max];i++)
  70     cout<<d[i]<<endl;
  71 }
  72 
  73 int main()
  74 {
  75      int id;
  76      id=0;
  77      int weight,speed;
  78      while(cin>>weight)
  79      {
  80          cin>>speed;
  81          a[id].w=weight;
  82          a[id].s=speed;
  83          a[id].id=id+1;
  84          id++;
  85      }
  86      n=id;   
  87      DP();
  88      //system("pause"); 
  89 }