导弹拦截 (LIS)

导弹拦截
链接：https://ac.nowcoder.com/acm/contest/24213/1012

题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入描述:
1行，若干个整数（个数≤100000）
输出描述:
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
示例1
输入

389 207 155 300 299 170 158 65

输出

6
2

题意：有一种导弹拦截系统，它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

思路：最多能拦截多少导弹，其实就是求最长不上升子序列的长度，第二问则用到狄尔沃斯定理，这就是把一个序列划分成最少的最长不上升子序列的个数就等于这个序列的最长上升子序列的长度。

AC代码:函数版单调递减子序,单调递增子序

#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+5;
int ans1, ans2;
int n=1;
int a[maxn];
int dp1[maxn], dp2[maxn];
int main(){while (cin>>a[n]) n++;n--;int ans1 = 1;dp1[ans1] = a[1];for (int i = 2; i <= n;i++){//单调递减子序if(a[i]<=dp1[ans1]) dp1[++ans1]=a[i];else{int temp = upper_bound(dp1 + 1, dp1 + ans1 + 1, a[i],greater()) - dp1;//返回小于value的值dp1[temp] = a[i];}}cout << ans1 << endl;int ans2 = 1;dp2[ans2] = a[1];for (int i = 2; i <= n;i++){//单调递增子序if(a[i]>dp2[ans2]) dp2[++ans2]=a[i];else{int temp = lower_bound(dp2 + 1, dp2 + ans2 + 1, a[i]) - dp2;dp2[temp] = a[i];}}cout << ans2 << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！