noip1999导弹拦截c++语言

#include<iostream>
#include<cstdio>
using namespace std;
int n=1,a[1000000][3],m=0,b[10000],r=1; 


int main()
{
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	while(cin>>a[n][1])n++;
	n=n-1;
	//n--;
	for(int i=1;i<=n;++i)
	{
	    //scanf("%d",&a[i][1]);
		a[i][2]=1;	
	}
	for(int i=n-1;i>0;--i)
	{
		for(int j=i+1;j<=n;++j)
		{
			if(a[i][1]>=a[j][1]&&a[i][2]<=a[j][2])
			a[i][2]=a[j][2]+1;
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i][2]>m)
		m=a[i][2];
	}
	
	b[1]=a[n][1];
	for(int i=n;i>0;--i)
	{
		for(int j=1;j<=r;++j)
		{
			if(j==r&&a[i][1]<b[j])
			{
				r++;
				b[r]=a[i][1];
				break;
			}
			if(a[i][1]>b[j])
			{
				b[j]=a[i][1];
				break;
			}
		}
		
	}
	cout<<m<<endl<<r;
	return 0;
}

拦截导弹(Noip1999)
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例：
INPUT
389 207 155 300 299 170 158 65
OUTPUT
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）

第一问就是用动态规划中的最长不下降子序列，很简单啦
第二问用贪心（真的不喜欢贪心啊啊/(ㄒoㄒ)/~~）从最后一颗开始设导弹系统，往前依次检查导弹高度是否大于系统中的最高导弹高度，是的话还要注意应用能拦截的所有系统中，最高导弹最低的那一套拦截。如果没有符合的系统，这枚导弹自成一系统

附上程序仅供参考

99年的noi是这样的哇(⊙o⊙)哦

原文链接：https://blog.csdn.net/qq_33990657/article/details/50678914