option=com_onlinejudge&Itemid=8&page=show_problem&problem=1072">链接：UVa 10131

题意：给定若干大象的体重及智商值。求满足大象体重严格递增，智商严格递减的序列的最大个数。

并打印随意一组取得最大值的序列的大象编号

分析：这个是LIS的应用，仅仅只是推断条件有两个，能够先对大象的体重排序，可是要打印路径。

那就必须得回溯求路径。能够直接逆序循环求，当然递归也是一个好的选择

#include<cstdio>

#include<algorithm>

using namespace std;

struct stu

{

    int size,iq,id;

}a[1005];

int dp[1005],path[1005],m;

int cmp(struct stu a,struct stu b)

{

    if(a.size!=b.size)

        return a.size<b.size;

    return a.iq>b.iq;

}

void back_path1(int i)

{

    if(path[i]!=i)

        back_path1(path[i]);

    printf("%d\n",a[i].id);

}

void back_path2(int i)

{

    if(m--){

        back_path2(path[i]);

        printf("%d\n",a[i].id);

    }

}

int main()

{

    int i=1,j,n,k,b[1005];

    while(scanf("%d%d",&a[i].size,&a[i].iq)!=EOF){

        a[i].id=i;

        i++;

    }

    n=i-1;

    sort(a+1,a+n+1,cmp);

    for(i=1;i<=n;i++){

        dp[i]=1;

        path[i]=i;

        for(j=1;j<i;j++)

            if(a[j].size<a[i].size&&a[j].iq>a[i].iq&&dp[j]+1>dp[i]){

                dp[i]=dp[j]+1;

                path[i]=j;

            }

    }

    k=1;

    for(i=2;i<=n;i++)

        if(dp[i]>dp[k])

            k=i;

    m=dp[k];

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

    b[1]=a[k].id;

    i=2;

    for(j=k;j>=1;j--)    //直接逆序循环求路径

        if(a[j].size<a[k].size&&a[j].iq>a[k].iq&&dp[k]==dp[j]+1){

            b[i++]=a[j].id;

            dp[k]--;

        }

    for(j=i-1;j>=1;j--)

        printf("%d\n",b[j]);

    //back_path1(k);             //能够用两种递归求路径

    //back_path2(k);

    return 0;

}