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;
}



上一篇:为什么3D模型的网格由很多三角形来组成


下一篇:linux下练习 c++ 有序二叉树