LIS题目的裸题
序列的最长递增子序列的长度，就是最少需要的导弹拦截系统
本题要点：
1、转态表示
dp[i] 表示以第i个数为结尾的最长递增子序列的长度
2、转移方程
dp[i] = max{0, dp[j]}, high[j] < high[i], 0 < j < i
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 10010;
int n, high[MaxN];
int dp[MaxN]; //dp[i] 表示以第i个数为结尾的最长递增子序列的长度void solve()
{memset(dp, 0 ,sizeof dp);dp[1] = 1;for(int i = 2; i <= n; ++i){int maxhigh = 0;for(int j = 1; j < i; ++j){if(high[j] < high[i]){maxhigh = max(maxhigh, dp[j]); }}dp[i] = maxhigh + 1;}int ans = 0;for(int i = 1; i <= n; ++i){ans = max(ans, dp[i]);}printf("%d\n", ans);
}int main()
{while(scanf("%d", &n) != EOF){for(int i = 1; i <= n; ++i){scanf("%d", &high[i]);}solve();}return 0;
}/* 8 389 207 155 300 299 170 158 65 *//* 2 */