hdu1160--最长有序子序列

数组a[]为待处理数组

f[]用于记录a[]数组中，以对应位置数据为结尾的最长有序序列长度

p[]用于记录a[]数组中，以对应位置数据为结尾的前一个数据位置

使用position记录最大长度位置

以a[]={1,4,7,2,5,8,3,6,9}，计算最长递增有序子序列为例

初始化f[]={1, 1, 1, 1, 1, 1, 1,1,1}，p[]={0,1,2,3,4,5,6,7,8}

计算f[i]时，f[i]=max(f[j]+1) ,(其中，a[i]>a[j],i>j>=0)，意思是以a[i]为结尾，找出在a[i]前比a[i]小的数据中以该数据为结尾的最大有序子序列长度max(f[j])，则以a[i]结尾的最大有序子序列长度为max(f[j])+1。计算同时定义p[i]=j，标志a[i]为结尾的最长子序列的前一个数据a[j]的位置。同时判断此时最大长度a[i]是否比当前最大长度max大，如果a[i]更大则更新position

a[]={1,4,7,2,5,8,3,6,9}

i=0   f[]={1,1,1,1,1,1,1,1,1},  p[]={0,1,2,3,4,5,6,7,8}

i=1   f[]={1,2,1,1,1,1,1,1,1},  p[]={0,0,2,3,4,5,6,7,8}  4>1，所以最大长度为2，position=1

i=2   f[]={1,2,3,1,1,1,1,1,1},  p[]={0,0,1,3,4,5,6,7,8}  7>4,7>1 其中4结尾的长度为2，所以最大长度为3，position=2

i=3   f[]={1,2,3,2,1,1,1,1,1},  p[]={0,0,1,0,4,5,6,7,8}  2>1 所以最大长度为2

i=4   f[]={1,2,3,2,3,1,1,1,1},  p[]={0,0,1,0,1,5,6,7,8}  5>1,5>4,5>2,其中以4结尾的长度为2，所以最大长度为3

i=5   f[]={1,2,3,2,3,4,1,1,1},  p[]={0,0,1,0,1,2,6,7,8}  8比前面的数据都大，所以最大长度为4，position=5

i=6   f[]={1,2,3,2,3,4,3,1,1},  p[]={0,0,1,0,1,2,3,7,8}  3>1,3>2,其中以2结尾的长度为2，所以最大长度为3

i=7   f[]={1,2,3,2,3,4,3,4,1},  p[]={0,0,1,0,1,2,3,4,8}  6>1,6>4,6>2,6>5,6>3,其中以5结尾长度为3，所以最大长度为4

i=8   f[]={1,2,3,2,3,4,3,4,5},  p[]={0,0,1,0,1,2,3,4,5}  9比前面数据都大，所以最大长度为5，position=8

在对所有a中元素循环过后，通过max记录下最后数据位置，以及p记录的前一个数据的位置，可以递归求出LIS

#include<stdio.h>
#include<algorithm>
using namespace std;
int f[10001];
int p[10001];
struct Mouse
{
    int w;
    int s;
    int n;
} M[10001];
bool compare(const Mouse &a, const Mouse &b)
{
    if(a.w==b.w)
        return a.s > b.s;
    else
        return a.w < b.w;
}
void printLIS(int max_l)
{
    if(p[max_l]==max_l)
    {
        printf("%d\n",M[max_l].n);
        return;
    }
    printLIS(p[max_l]);
    printf("%d\n",M[max_l].n);
}
int main()
{
    int i=1,max=0,max_l=0;
    while(scanf("%d %d",&M[i].w,&M[i].s)!=EOF)
    {
        f[i]=1;
        p[i]=i;
        M[i].n=i;
        i++;
    }
    sort(M+1,M+i,compare);
    for(int k=1; k<i+1; k++)
    {
        for(int j=1; j<k; j++)
        {
            if(M[j].s>M[k].s&&M[j].w<M[k].w)
            {
                if((f[j]+1)>f[k])
                {
                    f[k]=f[j]+1;
                    p[k]=j;
                    if(f[k]>max)
                    {
                        max = f[k];
                        max_l = k;
                    }
                }
            }
        }
    }
    printf("%d\n",max);
    printLIS(max_l);
    return 0;
}