防卫导弹（序列型DP） 解题日志

防卫导弹(dao)

【问题描述】

一种新型的防卫导弹可截击多个攻击导弹.它可以向前飞行,也可以用很快的速度向下飞行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行.但有一个缺点,尽管它发射时可以达到任意高度,但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹.现对这种新型 防卫导弹进行测试,在每一次测试中,发射一系列的测试导弹(这些导弹发射的间隔时间固定,飞行速度相同),该防卫导弹所能获得的信息包括各进攻导弹的高度,以及它们发射次序.现要求编一程序,求在每次测试中,该防卫导弹最多能截击的进攻导弹数量,一个导弹能被截击应满足下列两个条件之一:
它是该次测试中第一个被防卫导弹截击的导弹;
它是在上一次被截击导弹的发射后发射,且高度不大于上一次被截击导弹的高度的导弹.
【输入格式】

文件的第一行是一个整数N(0〈=N〈=4000),表示发射的进攻导弹数,以下1行，N个整数hi(0〈=hi〈=32767),表示进攻导弹的高度.文件中各行的行首,输入文件中给出的导弹是按发射顺序排列的.
【输出格式】

一个整数max,表示最多能截击的进攻导弹数。

【输入样例】

3

25

36

23

【输出样例：】

2

【代码日志】

#include<bits/stdc++.h>
using namespace std;
void FUCK(string name){
	string i=name+".in";
	string o=name+".out";
	freopen(i.c_str(),"r",stdin);
	freopen(o.c_str(),"w",stdout);
}
int n,ni[4500],li[4500];//第i颗导弹的最低 
int f[4500],hehe[4500];//第i颗导弹前面还有f[i]颗比他高的导弹 
int main(){
	FUCK("dao");
	//program here
	cin>>n;
	int maxi=0,maxn=0;
	f[0]=0;ni[0]=40000;
	for(int i=1;i<=n;i++){
		cin>>ni[i];
		f[i]=0;
		for(int j=i-1;j>=1;j--){
			if(ni[j]>=ni[i]){
				f[i]++;
			}
		}
		//cout<<"f["<<i<<"]="<<f[i]<<endl;
	}
	memset(hehe,0,sizeof(hehe));
	for(int i=1;i<=n;i++){
		hehe[f[i]]++;
		if(hehe[f[i]]>maxn){
			maxn=hehe[f[i]];
			maxi=f[i];
		}
	}
	for(int i=0;i<=n;i++){
		//cout<<"hehe["<<i<<"]="<<hehe[i]<<endl;
	}
	cout<<maxn<<endl;
	return 0;
}