/*某国为了防御敌国的导弹袭击，研发出一套导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发拦截
炮弹能够到达任意的高度，但是以后每一发拦截炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的多枚导弹来
袭。
/
输入描述
输入的第一行为导弹的个数n (0<n<10000),接下来的一行为导弹依次飞来的高度h（不大于
30000 的正整数）
输出描述
输出最多拦截的导弹个数。
输入样例
6
5 3 2 4 1 3
输出样例
4*/
1. n^2的
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int b[305];
int n, a[3005], sum = 0;
int dp[305];
int main(){
int j = 0, min;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 1; i < n; i++){
dp[0] = 1;
for(int j = 0; j < i; j++){
if(a[j] <= a[i] && dp[j] + 1 > dp[i]){
// b[i] = a[j];
dp[i] = dp[j] + 1;
}
}
// cout << b[i] << " ";
// cout << dp[i] << " ";
}
min = dp[0];
for(int i = 1; i < n; i++)
if(min < dp[i])
min = dp[i];
cout << min;
return 0;
}
2.下面是nlogn
#include <iostream>
using namespace std;
int search(int s, int *g, int low, int high){
int mid = 1;
while(low < high){
mid = (low + high) / 2;
if(g[mid] <= s)
low = mid + 1;
else
high = mid;
}
return low;
}
int main(){
int g[305], a[305], n;
cin >> n;
for(int i = 0; i < n; ++i)
cin >> a[i];
g[1] = a[0];
int len = 1, j = 0;
for(int i = 1; i < n; i++){
if(g[len] < a[i]) //如果a[i]比g的最后一个数组小就直接插在后面
j = ++len;
else
// j = search(a[i], g, 1, ++len); // （注意：这种情况长度不变，不能写成++len）
j = search(a[i], g, 1, len + 1); // 否则就插在g中比a[i]大的数中最小的那个数的位置即替换他
g[j] = a[i]; //用二分找的插入的位置
// cout << j << " "; //打印的是每次a[i]加入g 数组的位置（从1开始存入的）
}
cout << len;
return 0;
}