POJ 1836 Alignment 最长递增子序列(LIS)的变形

大致题意：给出一队士兵的身高，一开始不是按身高排序的。要求最少的人出列，使原序列的士兵的身高先递增后递减。

求递增和递减不难想到递增子序列，要求最少的人出列，也就是原队列的人要最多。

1 2 3 4 5 4 3 2 1

这个序列从左至右看前半部分是递增，从右至左看前半部分也是递增。所以我们先把从左只右和从右至左的LIS分别求出来。

如果结果是这样的：

　　A[i]={1.86 1.86 1.30621 2 1.4 1 1.97 2.2} //原队列

　　a[i]={1 1 1 2 2 1 3 4}

　　b[i]={3 3 2 3 2 1 1 1}

如果是A[1]~A[i]递增，A[i+1]~A[8]递减。此时就是求：a[1]~a[i]之间的一个值与b[i+1]~b[8]之间的一个值的和的最大值。

O(n^2)和O(nlogn)算法都可以过。

O(n^2)算法：

#include <iostream>

#include <cstdio>

using namespace std;

const int Max=1e3+;

int main()

{

    //freopen("in.txt","r",stdin);

    int n;

    scanf("%d",&n);

    double a[Max]={};

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

        scanf("%f",a+i);

    int l[Max]= {},r[Max]= {};

    l[]=r[n-]=;

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

    {

        int maxLen = ;

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

            if(a[j]<a[i])

                maxLen = max(maxLen,l[j]);

        l[i] = maxLen + ;

    }

    for(int i=n-; i>=; i--)

    {

        int maxLen=;

        for(int j=n-; j>i; j--)

            if(a[j]<a[i])

                maxLen=max(maxLen,r[j]);

        r[i]=maxLen+;

    }

    int maxlen=;

    for(int i=;i<n-;i++)

        for(int j=i+;j<n;j++)

            maxlen=max(maxlen,l[i]+r[j]);

    printf("%d\n",n-maxlen);

    return ;

}

O(nlogn)算法

#include <iostream>

#include <cstdio>

using namespace std;

const int Max=1e3+;

int l[Max]= {},r[Max]= {};

double B[Max];

int BinarySearch(double *a, double value, int n)

{

    int low = ;

    int high = n - ;

    while(low <= high)

    {

        int mid = (high + low) / ;

        if(a[mid] == value)

            return mid;

        else if(value<a[mid])

            high = mid - ;

        else

            low = mid + ;

    }

    return low;

}

int LIS_DP_NlogN(double *a, int n,int *Len)

{

    int nLISLen = ;

    B[] = a[];

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

    {

        if(a[i] > B[nLISLen - ])

        {

            B[nLISLen] = a[i];

            nLISLen++;

            Len[i]=nLISLen;

        }

        else

        {

            int pos = BinarySearch(B, a[i], nLISLen);

            B[pos] = a[i];

            Len[i]=pos+;

        }

    }

    return nLISLen;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n;

    scanf("%d",&n);

    double a[Max]={};

    double b[Max]={};

    l[]=r[]=;

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

    {

        scanf("%f",a+i);

        b[n-i-]=a[i];

    }

    LIS_DP_NlogN(a,n,l);

    LIS_DP_NlogN(b,n,r);

    int maxlen=;

    for(int i=;i<n-;i++)

        for(int j=n-i-;j>=;j--)

            maxlen=max(maxlen,l[i]+r[j]);

    printf("%d\n",n-maxlen);

    return ;

}