主题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160

题意：求体重下降。速度添加的样例最多有多少个

依据体重降序排一下，然后求速度的最长上升子序列 ，经典的LIS问题，记录一下路径

代码例如以下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1010;

struct cat{

    int w,s,id;

    bool operator < (const struct cat &b) const

    {

        return w>b.w;

    }

}c[maxn];

int q[maxn],path[maxn];

int bin_search(int x,int l,int r)

{

    while(l<=r){

        int mid=(l+r)>>1;

        if(c[q[mid]].s<x) l=mid+1;

        else r=mid-1;

    }

    return l;

}

int main()

{

    //freopen("out.txt","w",stdout);

    int cnt=0;

    while(cin>>c[cnt].w>>c[cnt].s) c[cnt].id=cnt+1,cnt++;

    sort(c,c+cnt);

    //cout<<"**************"<<endl;

    //for(int i=0;i<cnt;i++)

      //  cout<<c[i].w<<" "<<c[i].s<<" "<<c[i].id<<endl;

    //cout<<"**************"<<endl;

    int len=0;

    q[len++]=0;

    path[0]=0;

    for(int i=1;i<cnt;i++){

        if(c[i].s>c[q[len-1]].s){

            path[i]=q[len-1];

            q[len++]=i;

        }

        else{

            int idex = bin_search(c[i].s,0,len-1);

            path[i] = idex ? q[idex-1] : 0;

            q[idex] = i;

        }

    }

    printf("%d\n",len);

    printf("%d\n",c[q[len-1]].id);

    int tmp=q[len-1];

    while(--len){

        tmp = path[tmp];

        printf("%d\n",c[tmp].id);

    }

    return 0;

}

/*******

6008 1300

6000 2100

500 2000

1000 4000

1100 3000

6000 2000

8000 1400

6000 1200

2000 1900

*****/