洛谷题单指南-动态规划2-P1020 [NOIP1999 提高组] 导弹拦截

原题链接：https://www.luogu.com.cn/problem/P1020

题意解读：拦截系统发射导弹的高度依次不增，计算能拦截的最大导弹数以及需要几套拦截系统。

解题思路：

问题1：最多能拦截多少导弹？

由于发射导弹高度不增，所以求一个最长不增子序列即可得到最大拦截数。

方法一、O(n^2)做法：动态规划。

采用LIS最长上升子序列类似的模版代码，判断条件不同而已。

设a[]是所有导弹高度，

设dp[i]表示以第i个数结尾的最长不增子序列，

if(a[j] >= a[i]) dp[i] = max(dp[i], dp[j] + 1)  （ j 取 1~i-1）

dp数组的最大值即最长不增子序列的长度。

方法二、O(nlogn)做法：单调栈+二分。

根据最长上升子序列单调栈优化的原理：

枚举每一个导弹，存入一个不增的数组（用数组模拟栈是便于二分）；

如果导弹高度ai小于等于数组最后一个元素，则加入该数组尾部；

如果导弹高度ai大于数组最后一个元素，则通过二分查找到数组中<ai的第一个元素的位置，将该元素替换为ai；

最终，数组的长度即最长不增子序列的长度。

问题2：如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？

采用贪心算法：

用数组保存所有拦截系统当前的高度，该数组确保递增排序；

如果当前已经有拦截系统，用二分查找到第一个大于等于当前导弹高度的位置，用导弹高度更新拦截系统高度；

如果找不到能拦截当前导弹的系统，则增加一个，其高度为当前导弹的高度，追加到拦截系统数组尾部；

最终，数组的长度即最少配备的拦截系统数量。

100分代码（动态规划）：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N], cnt; //所有导弹高度
int dp[N]; //dp[i]是以第i个数结尾的最长不增子序列长度 
int s[N], top; //拦截系统

int main()
{
    int x;
    while(cin >> x)
    {
        a[++cnt] = x;
    }

    //计算最长不增子序列
    for(int i = 1; i <= cnt; i++)
    {
        dp[i] = 1;
        for(int j = 1; j < i; j++)
        {
            if(a[j] >= a[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int maxx = 0;
    for(int i = 1; i <= cnt; i++) maxx = max(maxx, dp[i]);
    cout << maxx << endl;

    //计算导弹系统数
    for(int i = 1; i <= cnt; i++)
    {
        if(top == 0 || a[i] > s[top]) s[++top] = a[i]; //如果没有拦截系统或者已有拦截系统都无法拦截，就发射一个，高度等于当前导弹高度
        else //否则二分找到第一个>=a[i]的位置，进行替换，表示拦截到导弹后，高度减少,这里即体现贪心思想，用一个刚好能拦截的系统进行拦截
        {
            int l = 1, r = top, ans = -1;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(s[mid] >= a[i])
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            s[ans] = a[i];
        }
    }
    cout << top << endl;

    return 0;
}

100分代码（单调栈+二分）：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N], cnt; //所有导弹高度
int l[N], topl; //l保存最长不增子序列，是一个单调不增的数组
int s[N], tops; //拦截系统

int main()
{
    int x;
    while(cin >> x)
    {
        a[++cnt] = x;
    }

    //计算最长不增子序列
    for(int i = 1; i <= cnt; i++)
    {
        if(topl == 0 || l[topl] >= a[i]) l[++topl] = a[i]; //如果数组空或者栈顶比a[i]小，把a[i]入栈
        else
        {
            int left = 1, right = topl, ans = -1;
            while(left <= right)
            {
                int mid = (left + right) >> 1;
                if(l[mid] < a[i]) //找到<a[i]的第一个
                {
                    ans = mid;
                    right = mid - 1;
                }
                else left = mid + 1;
            }
            l[ans] = a[i]; 
        }
    }
    cout << topl << endl;

    //计算导弹系统数
    for(int i = 1; i <= cnt; i++)
    {
        if(tops == 0 || a[i] > s[tops]) s[++tops] = a[i]; //如果没有拦截系统或者已有拦截系统都无法拦截，就发射一个，高度等于当前导弹高度
        else //否则二分找到第一个>=a[i]的位置，进行替换，表示拦截到导弹后，高度减少,这里即体现贪心思想，用一个刚好能拦截的系统进行拦截
        {
            int left = 1, right = tops, ans = -1;
            while(left <= right)
            {
                int mid = (left + right) >> 1;
                if(s[mid] >= a[i])
                {
                    ans = mid;
                    right = mid - 1;
                }
                else left = mid + 1;
            }
            s[ans] = a[i];
        }
    }
    cout << tops << endl;

    return 0;
}