题目大意
给定一串导弹的高度序列（按到达顺序）。
1）求最多能用多少套“拦截系统”把所有导弹拦截完（每套系统只能拦截一个不升的序列）。
2）求这串序列的最长严格上升子序列长度。
输出两行分别为上述两个答案。
AC代码
根据题意，我们要求最长单调子序列
个人认为讲的比较好的leetcode题解，贪心
https://leetcode.com/problems/longest-increasing-subsequence/solutions/1326308/c-python-dp-binary-search-bit-segment-tree-solutions-picture-explain-o-nlogn
这种做法即维护了接纳信息，又维护了长度信息，一举两得。
然后注意写a.begin()，不要写begin（a），前面的是C++98写法
AC. https://www.luogu.com.cn/record/183637393
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll num,A[N];
vector<ll> sub,sys;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n=0;
while (cin>>num) {
++n;
A[n]=num;
}
for(int i=1;i<=n;++i) {
if(i==1)
sub.push_back(A[1]);
else {
if(A[i]<=sub.back()) {
sub.push_back(A[i]);
continue;
}
ll idx=upper_bound(sub.begin(),sub.end(),A[i],greater<int>())-sub.begin();
sub[idx]=A[i];
}
}
for(int i=1;i<=n;i++) {
if(i==1) {
sys.push_back(A[i]);
}else {
ll idx=lower_bound(sys.begin(),sys.end(),A[i])-sys.begin();
if(idx>=sys.size())
sys.push_back(A[i]);
else
sys[idx]=A[i];
}
}
cout<<sub.size()<<endl;
cout<<sys.size()<<endl;
return 0;
}
|
心路历程（WA，TLE，MLE……）