导弹问题.cpp

acm中的导弹防御算法

#include"stdio.h"

void main()
{
	int i,n,j;
	int maxman=0,first=1;
	int max[4000],h[4000],next[4000]={0};
	printf("请输入导弹的个数\n");
	scanf("%d",&n);
	printf("请分别输入导弹的高度\n");
	for(i=1;i<=n;i++)
		scanf("%d",&h[i]);
	printf("输出被拦截导弹的个数\n");
for (i=n;i>0;i--)
{
	max[i]=1;next[i]=0;
	if (i!=n)
	{
		for(j=i+1;j<=n;j++)
		{
			if (h[i]>=h[j])
			{	
				if (max[i]<max[j]+1)
				{
					max[i]=max[j]+1;
					next[i]=j;
					
				}
			}
		
		}
	
	}
		if (max[i]>maxman)
			{
				maxman=max[i];
				first=i;
			}	

}
	printf("%d\n",maxman);
	printf("输出序列号\n");
	while(first!=0)
	{
	for(i=0;i<=n;i++)
		{

			if(first!=0)
		{
			printf("%d\n",first);
			first=next[first];
		}
		}
	}
}