ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

P1020　[NOIP 1999 提高组] 导弹拦截

来源：洛谷 ★ 1500

DP贪心自评已掌握
本题活力0.11本次有不同于此前记录的心得，计入额外复盘活力

算法如山行则将至

查看原题王梓豪 的主页

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

代码

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int temp;
    vector<int> a;

    while (cin >> temp)
    {
        a.emplace_back(temp);
    }
    vector<int> dp;

    for (int i = 0; i < (int)a.size(); i++)
    {
        int temp = -a[i];
        int pos = upper_bound(dp.begin(), dp.end(), temp) - dp.begin();

        if (pos == (int)dp.size())
        {
            dp.emplace_back(temp);
        }
        else
        {
            dp[pos] = temp;
        }
    }
    int ans = dp.size();
    dp.clear();
    for (int i = 0; i < (int)a.size(); i++)
    {
        int pos = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();

        if (pos == (int)dp.size())
        {
            dp.emplace_back(a[i]);
        }
        else
        {
            dp[pos] = a[i];
        }
    }
    int cnt = dp.size();
    cout << ans << endl;
    cout << cnt << endl;
    return 0;
}