解题报告 P1020 导弹拦截【NOIP1999TG】

题目内容

P1020

大意：求最长不下降子序列和最长上升子序列。

解题思路

半年前的坑，今天给填上。不难想出 O(n^2) 的做法：设 f_i 为以 a_i 结尾的 LIS 的长度，则有状态转移方程

f_i= \max_{j

每次都往前面扫描一遍，复杂度 O(n^2)

#include <cstdio>
#include <cstring>
#define maxn 100009
int a[maxn],b[maxn],h[maxn];

using namespace std;
int main()
{
    int ans1=0;
    memset(a,0,sizeof(a));
    memset(b,1,sizeof(b));
    memset(h,0x7ffffff,sizeof(h));
    int n=1,m=0;//n:the num of missiles, m:the num of sys
    while(scanf("%d",&a[n])!=EOF)
    {
        int l=0;
        for(int i=n-1;i>0;i--)
        {
            if(a[i]>=a[n]&&b[i]>l)
                l=b[i];
        }
        b[n]=l+1;
        if(b[n]>ans1) ans1=b[n];
        int x=0;
        for(int k=1;k<=n;k++)
        {
            if(h[k]>=a[n])
                if(x==0)
                    x=k;
                else if(h[k]<h[x])
                    x=k;
        }
        if(x==0)
        {
            m++;
            x=m;
        }
        h[x]=a[n];
        n++;
    }
    printf("%d %d\n",ans1,m);
    return 0;
}

当然这个算法太慢了，过不了洛谷的后面 10 个极限数据，因此我们需要 O(n\log n) 的做法，这个算法结合了二分查找和贪心。

如果我们此时设 f_i 表示长度为 i 的 LIS 的结尾的数字的话，思考：是不是当 f_i 越小，才越方便后面的数接进这个 LIS 呢，具体维护 f_i 的方法如下：

从 a_2 开始枚举每一个 a_i，如果新的 a_i 能接上这个已知最长的 LIS，那就接上去，否则就在 f 数组里面寻找能让 a_i 接上的 LIS 的长度，由于 f 数组一定满足单调递减，所以只需要利用二分查找在里面寻找第一个 f_j 使得 f_j\ge a_i 就可以了，然后更新对应的 f_j 即可。二分查找可以使用 STL 来偷懒降低代码复杂度。

该算法的复杂度为 O(n\log n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=100000+5;
int f1[maxn],f2[maxn],a[maxn],tot;

bool cmp(const int& a,const int& b)
{
    return a>b;
}

int main()
{
    memset(f1,0x7fffffff,sizeof(f1));
    memset(f2,0x7fffffff,sizeof(f2));
    while(scanf("%d",&a[++tot])!=EOF);
    f1[1]=a[1],f2[1]=a[1];
    //f[i]存储长度为i的序列的尾元素
    int len1=1,len2=1;//len表示查询到的LIS的最长长度
    for(int i=2;i<tot;i++)
    {
        if(a[i]<=f1[len1])//如果当前的a[i]可以接在最长的LIS的末尾
            f1[++len1]=a[i];//就接上去
        else
        {
            int p1=upper_bound(f1+1,f1+1+len1,a[i],cmp) - f1;
            //否则找到第一个大于他的
            f1[p1]=a[i];//然后接在后面，更新最小值
        }
        if(a[i]>f2[len2])
            f2[++len2]=a[i];
        else
        {
            int p2=lower_bound(f2+1,f2+len2+1,a[i])-f2;
            f2[p2]=a[i];
        }
    }
    printf("%d\n%d\n",len1,len2);
    return 0;
}