
1590年法国国王亨利四世率领的雨格诺派军队,在伊夫里战役中击败夏尔·德·吉斯的天主教联盟。
1794年美国机械工程师伊莱·惠特尼(图)发明能够快速分离棉花纤维和种子的轧棉机,并取得专利权。
1879年:阿尔伯特·爱因斯坦,美国物理学家,1921年诺贝尔物理学奖得主(1955年逝世)
1945年英国皇家空军对纳粹德国比勒费尔德的铁路高架桥首次使用重达2.2万磅的大满贯炸弹轰炸。
1978年以色列国防军开始入侵并占领黎巴嫩南部,这迫使巴勒斯坦解放组织撤往利塔尼河以北。
送别在下的“一辈子”服务器:192.144.164.198后,伤感,是的,失落,是的。
现在,新的服务器新的生活!
讨厌宝塔强制登陆,用其一劳永逸:
rm -f /www/server/panel/data/bind.pl
题目描述
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入格式输入数据为两行,
第一行为导弹的数目N(n<=1000)
第二行导弹依次飞来的高度,所有高度值均为不大于30000的正整数。 输出格式输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开. 样例输入
8
389 207 155 300 299 170 158 65
样例输出
6 2
#include<iostream>
using namespace std;
int n;
int h[1001],ht[1001],best[1001];
int ans=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
best[0]=0x7fffffff;
for(int i=1;i<=n;i++)
for(int j=ans;j>=0;j--)
if(best[j]>=h[i]){best[j+1]=h[i];ans=max(ans,j+1);break;}
cout<<ans;
ans=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=ans;j++)
{
if(ht[j]>=h[i]){ht[j]=h[i];break;}
}
if(ht[ans]<h[i])ht[++ans]=h[i];
}
cout<<' '<<ans;
return 0;
}