防卫导弹(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; }