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

2018-06-17 23:37:33来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

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+5;

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    double a[Max]={0};
    for(int i=0; i<n; i++)
        scanf("%f",a+i);
    int l[Max]= {0},r[Max]= {0};
    l[0]=r[n-1]=1;
    for(int i = 1; i < n; i++)
    {
        int maxLen = 0;
        for(int j = 0; j < i; j++)
            if(a[j]<a[i])
                maxLen = max(maxLen,l[j]);
        l[i] = maxLen + 1;
    }
    for(int i=n-2; i>=0; i--)
    {
        int maxLen=0;
        for(int j=n-1; j>i; j--)
            if(a[j]<a[i])
                maxLen=max(maxLen,r[j]);
        r[i]=maxLen+1;
    }
    int maxlen=0;
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            maxlen=max(maxlen,l[i]+r[j]);
    printf("%d\n",n-maxlen);
    return 0;
}

O(nlogn)算法

#include <iostream>
#include <cstdio>
using namespace std;

const int Max=1e3+5;
int l[Max]= {0},r[Max]= {0};
double B[Max];
int BinarySearch(double *a, double value, int n)
{
    int low = 0;
    int high = n - 1;
    while(low <= high)
    {
        int mid = (high + low) / 2;
        if(a[mid] == value)
            return mid;
        else if(value<a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int LIS_DP_NlogN(double *a, int n,int *Len)
{
    int nLISLen = 1;
    B[0] = a[0];
    for(int i = 1; i < n; i++)
    {
        if(a[i] > B[nLISLen - 1])
        {
            B[nLISLen] = a[i];
            nLISLen++;
            Len[i]=nLISLen;
        }
        else
        {
            int pos = BinarySearch(B, a[i], nLISLen);
            B[pos] = a[i];
            Len[i]=pos+1;
        }
    }
    return nLISLen;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    double a[Max]={0};
    double b[Max]={0};
    l[0]=r[0]=1;
    for(int i=0; i<n; i++)
    {
        scanf("%f",a+i);
        b[n-i-1]=a[i];
    }
    LIS_DP_NlogN(a,n,l);
    LIS_DP_NlogN(b,n,r);
    int maxlen=0;
    for(int i=0;i<n-1;i++)
        for(int j=n-i-2;j>=0;j--)
            maxlen=max(maxlen,l[i]+r[j]);
    printf("%d\n",n-maxlen);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:[NOIP2009] 靶形数独(搜索+剪枝)

下一篇:Qt中QScrollArea类的简单使用心得