您的位置: 首页  >  文章  >  luogu1020：导弹拦截：最长上升子序列+单调队列

luogu1020：导弹拦截：最长上升子序列+单调队列

分类: 文章 • 2025-01-10 17:31:58

题目连接

  • 该题是luogu试炼场的2-16：T1

题目大意

  1. 有一个 n 个元素的序列，求其中的“最长不上升子序列” 和“最长上升子序列”
  2. 200分的数据是：n=100000；

题目分析

  • DP的起手题，最长上升子序列问题：

  • 题意分析：

  • 问题1：一个系统，攻击的高度只能持平或者衰减，所以用暴力的思维理解，当前是 x 个导弹，如果（x -> n ）个导弹中，希望尽可能多的导弹能满足要求；
    luogu1020：导弹拦截：最长上升子序列+单调队列

  • 问题2：需要多少个这样的系统？本质和走楼梯一样，前面的小高峰，无法解决后面的大高峰的问题。
    luogu1020：导弹拦截：最长上升子序列+单调队列

  • 思路1：暴力枚举（100分）

  • 思路2：单调队列优化（200分）

思路1：暴力枚举 O (n2)

  1. 对于问题1：暴力求最长不上升子序列：从后往前枚举 i ，对 [i+1，n] 的数据匹配，看看能否获得更多的 小于等于i的值；
  2. 对于问题2：暴力求最长上升子序列：从前往后枚举 i ，对 [1，i-1] 的数据匹配，看看能否获得更多的 小于 i 的值；
  3. 思路非常简单，代码非常暴力。

代码：

luogu说100分

//luogu1020:导弹拦截
//解法1：简单DP：O（n*n）
//求一个最长不上升子序列，再求一个最长上升子序列
 
#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int n=0,s1=0,s2=0,f[mx],a[mx];

int main()
{
    while(scanf("%d",&a[++n])!=EOF);
    n--;
    
    for(int i=n;i>=1;i--)//以 i 开头的，最长不上升 
    {
        f[i]=1;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<=a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
        s1=max(s1,f[i]);//求出最长的 
    }
    
    for(int i=1;i<=n;i++)//以 i 结尾，的最长上升 
    {
        f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
        s2=max(s2,f[i]);
    }
    
    printf("%d\n%d",s1,s2);
    
    return 0;
}

思路2：单调队列优化 O（nlogn）

用一个单调队列来存储当前的最优解的状态；
单调队列的进队有2种方法：

  1. 如果比队尾的值更优，直接进队尾；
  2. 否则，利用二分在队伍中找到适合的位置。
    再次强调：二分一定要熟练，清晰代码的每一个细节。

PS，STL可以完美解决，作为特别放送：

代码2：

  • luogu说：200分
//luogu1020:导弹拦截 200分 

//解法2：单调队列的思维进行优化：O（n*logn）
// STL实现 https://www.luogu.org/blog/w1049/solution-p1020

//1 用一个单调队列来存储这个 序列
//2 进队有两种情况：
// 1）直接进队尾；
// 2）在队伍中找到更优的替代位置 (二分查找) 
 
#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int n=0,f[mx],a[mx],wei;

void so1()//最长不上升 
{
    wei=0;
    f[0]=mx;//队列最左边
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=f[wei]) { f[++wei]=a[i]; continue; }//队列增长
        
		//二分查找“比他小又最靠左”的值：替换 
        int l=1,r=wei;
        while(l+3<r)
        {
            int mid=(l+r)/2;

            if(a[i]<=f[mid]) l=mid;
            else r=mid;
        } 
        for(int j=l;j<=r;j++) 
		{
			if(f[j]<a[i]) { f[j]=a[i];break; }
		}
    }
    printf("%d\n",wei); 
}

void so2()//最长上升 
{
    wei=0;
    f[0]=0;//队列最左边
    for(int i=1;i<=n;i++)
    {	
		
		
        if(a[i]>f[wei]) { f[++wei]=a[i];continue; }//队列增长
        	
		//二分查找“比他大又最靠左”的值：替换 
	    int l=1,r=wei;
	    while(l+3<r)
	    {
	        int mid=(l+r)/2;
	
	        if(a[i]>=f[mid]) l=mid;
	        else r=mid;
	    } 
	    for(int j=l;j<=r;j++) 
		{
			if(f[j]>=a[i]) { f[j]=a[i];break; }//单调上升队列，所以不能相同 
		}		
    }
    printf("%d\n",wei); 
}

int main()
{
    while(scanf("%d",&a[++n])!=EOF);
    n--;
    
    so1();
    so2();
    
    return 0;
}

相关推荐