记录编号	193407	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-10-14 18:57:10	内存使用	0.34 MiB

#include <iostream>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

ifstream fin("missile.in");
ofstream fout("missile.out");
#define cin fin
#define cout fout
const long long MAXN(1001);
long long dpa[MAXN], ansb = 0, ddh[MAXN], h[MAXN], ansa = 0;

main()
{
//	cout << sizeof(dpa) / 1024.0 / 1024.0 << endl;
	long long n = 1;
	while (cin >> h[n])
		++n;
	fin.close();
	
	--n;
	fill(dpa + 1, dpa + n + 1, 1);
	for (long long i = 1; i <= n; ++i){
		for (long long j = 1; j < i; ++j)
			if (h[j] >= h[i])
				dpa[i] = max(dpa[i], dpa[j] + 1);
		ansa = max(ansa, dpa[i]);
	}
	for (long long i = 1; i <= n; ++i){
		long long nhigh = INT_MAX, usedd;
		for (long long j = 1; j <= ansb; ++j)
			if (ddh[j] >= h[i] && ddh[j] < nhigh){
				usedd = j;
				nhigh = ddh[j];
			}
		if (nhigh == INT_MAX)
			ddh[++ansb] = h[i];
		else
			ddh[usedd] = h[i];
	}
	
	cout << ansa << endl << ansb;
	fout.close();
//	for (; ; );
}