题目
现在有一种拦截系统，第一发拦截可以是任意高度，但是之后的拦截高度不能比上次高。为了拦截下所有的炮弹，最少需要准备几套拦截系统？
思路
可能是语文没学好吧，一开始被题意卡了一下。（而且题目连数据范围也没给???）
比如这种数据：
Input
7 500 400 300 350 120 200 150
Output
2
HINT
第一套系统：①500 ②400 ③300 ⑥200 ⑦150
第二套系统：④350 ⑤120
比赛的时候感觉贪心可做。但又很像动态规划里的LIS，好在前段时间组队赛的时候看了看板子上的LIS
动态规划：最长上升子序列（LIS）
LIS（最长上升子序列）问题的三种求解方法以及一些例题
赛后想了想关于贪心的思路：对于当前的导弹，若当前所有的拦截系统都不能挡住，则新开一个拦截系统。若有，就在已有的拦截系统里寻找一个比他高同时最接近他高度的系统（尽量减少损失），并更新该系统为高度最低的导弹。
AC代码（dp - LIS）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mst(a) memset(a, 0, sizeof(a))
using namespace std;
const int maxn = 1e4+5;
int a[maxn], dp[maxn];
int main()
{
int T, mmax, num;
while( ~scanf("%d",&T) ){
if(T==0){
printf("0
");
continue;
}
mst(dp);
mst(a);
for( int i = 0; i < T; i++ ){
scanf("%d",&a[i]);
dp[i] = 1;
}
for( int i = 1; i < T; i++ ){
for( int j = 0; j < i; j++ ){
if( a[j] < a[i] ){
dp[i] = max(dp[i], dp[j]+1);
}
}
}
sort(dp, dp+T);
printf("%d
",dp[T-1]);
}
return 0;
}AC代码（贪心）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mst(a) memset(a, 0, sizeof(a))
using namespace std;
const int maxn = 1e4+5;
const int INF = 0x3f3f3f3f;
int a[maxn], dp[maxn];
int main()
{
int n, cnt, dmin;
bool flag;
while( ~scanf("%d",&n) ){
mst(a);
mst(dp);
for( int i = 0; i < n; i++ )
scanf("%d", &a[i]);
cnt = 0;
dp[cnt] = a[0];
int mark;
for( int i = 1; i < n; i++ ){
dmin = INF;
flag = false;
for( int j = 0; j <= cnt; j++ ){
if( a[i] < dp[j] ){
int d = dp[j] - a[i];
if( d < dmin ){
dmin = min(dmin, dp[j]-a[i]);
mark = j;
}
flag = true;
}
}
if( flag ) dp[mark] = a[i];
else dp[++cnt] = a[i];
}
printf("%d
",cnt+1);
}
return 0;
}