【Acwing1010】拦截导弹（LIS+贪心）题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Acwing1010】拦截导弹（LIS+贪心）题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

【Acwing1010】拦截导弹（LIS+贪心）题解,算法综合,Acwing,动态规划,算法,c++,acwing

看本文需要准备的知识

1.最长上升子序列（lis）的算法思想和算法模板

2.简单了解贪心算法的思想

思路分析

本题有两问，第一问直接用lis的模板即可，下面重点看第二问

思路是贪心：

贪心流程：

从前往后扫描每一个数，对于每个数：

情况一：如果现有的子序列的结尾都小于当前的数，则创建子序列

情况二：将当前的数放到结尾大于等于它的最小的子序列后面

举个例子：

360 322 555 222.....

从左到右遍历上面序列，当遍历到222的时候，此时已经存在了两个子序列“360 322”和“555”，两个子序列的结尾分别是322和555，其中322是大于等于222且是“322和555”中最小的数，所以把222放在序列“360 322”的后边！

贪心证明：

A表示贪心算法得到的序列个数，B表示最优解

B<=A 显然

如何证明B>=A?利用调整法：

【Acwing1010】拦截导弹（LIS+贪心）题解,算法综合,Acwing,动态规划,算法,c++,acwing

如上图所示，假设a的后面是利用贪心算法插入的一个数，b的后面是最优解插入的一个数

在这两个序列后面补齐之后：

【Acwing1010】拦截导弹（LIS+贪心）题解,算法综合,Acwing,动态规划,算法,c++,acwing

因为a是最优解的插法，所以b>=a

可以把x及后面的序列做交换，导致最优解变成了贪心解，并且总序列个数不变，所以B>=A

完整代码：文章来源地址https://www.toymoban.com/news/detail-727691.html

#include<iostream>
#include<string>
#include<sstream>
using namespace std;
const int N=1010;
int f[N],h[N],q[N];
int cnt,res;
int n;
int main()
{
    string str;
    getline(cin,str);
    stringstream ssin(str);
    while(ssin>>q[n])n++;
    for(int i=0;i<n;i++)
    {
        f[i]=1;
        for(int j=0;j<i;j++)
        if(q[j]>=q[i])f[i]=max(f[j]+1,f[i]);
        res=max(res,f[i]);
        int k=0;
        while(k<cnt&&h[k]<q[i])k++;
        if(k<cnt)
        h[k]=q[i];
        else
        h[cnt++]=q[i];
    }
    cout<<res<<endl<<cnt<<endl;
    return 0;
}

到了这里，关于【Acwing1010】拦截导弹（LIS+贪心）题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！