【问题描述】
某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。
【输入形式】
每组输入有两行,
第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),
第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。
【输出形式】
每组输出只有一行,包含一个整数,表示最多能拦截多少枚导弹。
【样例输入】
8 300 207 155 300 299 170 158 65
【样例输出】
6
【思路分析】
LIS。线性dp+二分,板子题。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <cstring>
#include <iomanip>
#include <set>
#include <queue>#define i64 long longusing namespace std;i64 LIS(i64 arr[], i64 n) {i64 dp[n], len = 0;dp[0] = arr[0];for (int i = 1; i < n; ++i) {if (arr[i] >= dp[len]) dp[++len] = arr[i];else *(lower_bound(dp, dp + len, arr[i])) = arr[i];}return len + 1;
}void solve() {i64 n;cin>>n;i64 arr[n];for (int i = n-1; i >= 0; --i) cin>>arr[i];cout<<LIS(arr,n);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;
// cin >> t;while (t--) {solve();}return 0;
}