最少拦截系统(LIS)

思路：最长单调递减子序列的个数 就是等于 最长单调递增子序列的长度(因为是递增这些序列要么独立驾一个炮台，要么加到其他的序列中去，因为它们是递增，那么不可能加到同一序列中去，最会最多加的炮台数量就是等于他们的长度)，所以这题就转化求最长上升子序列的长度了。
代码：

#include<bits/stdc++.h>
using namespace std;

int n;
int a[10000];
int main(){
	while(scanf("%d",&n)!=EOF){
		int dp[1000];dp[1] = 1;
		int ans = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
			int M = 0;
			for(int j = 1; j < i ; j++){
				if(a[j] < a[i]){
					M = max(M,dp[j]);
				}
			}
			dp[i] = M + 1;
			ans = max(dp[i],ans);
		}
		cout<<ans<<endl;
	}
}