洛谷 P1020 导弹拦截

很经典的DP题

不会 :lei:

原题链接:https://www.luogu.org/problem/P1020

俩问:一是求最长不上升子序列长度

二是求最长上升子序列长处

看了一个大佬的题解,学了一种O(nlogn)的解法

以下是dalao原话:
首先我们需要一个数组a,存储从第1个到第n个导弹的高度

然后一个数组d(其实是个栈),存储不上升序列

把a中的每个元素挨个加到d里面:

(a中第i个元素为a[i],d长度为len,d中最后一个(也是最小的一个)为d[len])

如果a[i] <= d[len],说明a[i]可以接在d后面(而整个d还是有序的),那就简单粗暴地把a[i]丟进d:

如果a[i] > d[len],说明a[i]接不上

但是我们发扬瞎搞精神接的上要接,接不上创造条件也要接!

强行把a[i]塞进去:

在d中找到第一个小于a[i]的数,把它踹了,用a[i]代替它!(为什么正确在下面)

假设这个数是y,怎样踹掉它呢?

很明显,我们需要使用lower_bound和upper_bound来查找

为什么正确

显然成立

如果y末尾,由于y < a[i],所以y后面能接的不如a[i]多,y让位给a[i]可以让序列更长

如果y不在末尾,那y有生之年都不会再被用到了,直接踹了y就行,y咋样,who care?

#include <bits/stdc++.h>
using namespace std;
int a[100100];
int e[100100];
int c[100100];
int main()
{
    int l=0;
    while(~scanf("%d",&a[++l]));
    l--;
    int xp=0,cp=0;
    e[xp++]=a[1];
    c[cp++]=a[1];
    for(int i=2;i<=l;i++)
    {
        if(a[i]<=e[xp-1])
        {e[xp++]=a[i];}
        else
        {
            int op=upper_bound(e,e+xp,a[i],greater<int>())-e;
            e[op]=a[i];
        }
        if(a[i]>c[cp-1])
        {c[cp++]=a[i];}
        else
        {
            int op=lower_bound(c,c+cp,a[i])-c;
            c[op]=a[i];
        }
    }
    cout<<xp<<endl<<cp;
    return 0;
} 

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注