HDU(1257)——最少拦截系统(dp问题）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[10001],h[10001];
int main(){
	int n,i,j,sum;
	while(~scanf("%d",&n)){
		memset(a,0,sizeof(a));  memset(h,0,sizeof(h));
		for(i=1;i<=n;i++)
			scanf("%d",&h[i]);
		int max=-1;
		a[1]=1;
		for(i=2;i<=n;i++){
			max=-1;
			for(j=1;j<i;j++){
				if(h[i]<=h[j]){
					if(max<a[j]+1) 
						max=a[j]+1;
				}
			}
			a[i]=max;
		}
		//找出a[1]~a[n]中的最大值即可； 
		sort(a+1,a+1+n);
		printf("%d\n",a[n]);
		int sys[10001]={0};
		int tail=1,minheight,select;
		sys[1]=h[1];
		//i代表的是第几个导弹； 
		for(i=2;i<=n;i++){
			minheight=99999999;
			for(j=1;j<=tail;j++){
				//判断当前系统的高度是否大于来的导弹的高度；
				//下面那部分是为了选择一套最优的方案，即当情况都成立时，选择高度较低的那个系统； 
				if(sys[j]>=h[i])
					if(sys[j]<minheight){
						minheight=sys[j];  select=j;
					}
			}
			//说明当前系统都无法满足，那么就要另外开启系统了， 
			if(minheight==99999999){
				tail++;  sys[tail]=h[i];
			}
			//否则的话更新该系统的高度值，因为打了一次之后高度就会比原来的低了； 
			else  sys[select]=h[i];
		}
		printf("%d\n",tail);
	}
}