空间范围,不过那种导弹拦截系统有二个弱点

104肆 拦截导弹

19九六年NOIP全国际结盟赛提升组

时限: 一 s

空间限制: 12九千 KB

标题等级 : 黄金 戈尔德

 

标题叙述 Description

   
某国为了防卫敌国的导弹袭击,发展出一种导弹拦截连串。可是那种导弹拦截系统有1个缺陷:固然它的首头阵炮弹能够到达任意的莫斯中国科学技术大学学,可是随后每一发炮弹都无法超过前一发的惊人。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以唯有一套系统,由此有相当大也许或不能够阻挡全体的导弹。

  

输入描述 Input Description

输入导弹依次飞来的万丈(雷达给出的中度数据是不当先20000的正整数)

  

输出描述 Output Description

出口那套系统最多能拦截多少导弹,假设要阻拦全数导弹至少要配备多少套那种导弹拦截类别。

样例输入 Sample Input

389 207 155 300 299 170 158 65 

样例输出 萨姆ple Output

6

2

多少范围及提示 Data Size & Hint

导弹的可观<=三千0,导弹个数<=20

思路:求最长不下跌子类别与最长不回升子连串。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=20+5;
 5 int dp[maxn],dp2[maxn],high[maxn],ans=0,ans2=0,cnt=0;
 6 int main()
 7 {
 8     while(cin>>high[cnt])
 9     {
10         dp[cnt]=1;
11         dp2[cnt]=1;
12         cnt++;
13     }
14     for(int j=0; j<cnt; j++)
15     {
16         for(int k=0; k<j; k++)
17         {
18             if(high[k]>=high[j])
19                 dp[j]=max(dp[j],dp[k]+1);
20             if(high[k]<=high[j])
21                 dp2[j]=max(dp2[j],dp2[k]+1);
22         }
23         ans=max(ans,dp[j]);
24         ans2=max(ans2,dp2[j]);
25     }
26     cout<<ans<<endl<<ans2<<endl;
27 }

 

 时间限制: 1 s

 空间限制: 128000KB

 标题等级 : 黄金
戈尔德

难题叙述 Description

   
某国为了防卫敌国的导弹袭击,发展出一种导弹拦截连串。可是那种导弹拦截体系有三个缺点:尽管它的率头阵炮弹可以到达任意的万丈,不过随后每一发炮弹都不可能压倒前一发的中度。某天,雷达捕捉到敌国的导弹来袭。由于该种类还在试用阶段,所以唯有1套系统,由此有望无法阻止全部的导弹。

  

输入描述 Input Description

输入导弹依次飞来的可观(雷达给出的可观数据是不超越贰仟0的正整数)

  

输出描述 Output Description

输出那套系统最多能拦截多少导弹,如若要阻拦全体导弹至少要安顿多少套那种导弹拦截种类。

样例输入 萨姆ple Input

389 207 155 300 299 170 158 65 

样例输出 Sample Output

6

2

数据范围及提醒 Data Size & Hint

导弹的中度<=两千0,导弹个数<=20

 

序列dp

率先次找最长下落子体系 

其次次找最长上涨子体系

屠龙宝刀点击就送

#include <cstdio>
int f1[25],f2[25],a[25],cnt=0,ans1,ans2;
int max(int a,int b){return a>b?a:b;} 
int main()
{
    while(scanf("%d",&a[++cnt])!=EOF) f1[cnt]=f2[cnt]=1;cnt--;
    for(int i=1;i<cnt;i++)
    {
        for(int j=i+1;j<=cnt;j++)
        {
            if(a[j]<=a[i]) f1[j]=max(f1[i]+1,f1[j]);
            ans1=max(ans1,f1[j]);
        }
    }
    for(int i=1;i<cnt;i++)
    {
        for(int j=i+1;j<=cnt;j++)
        {
            if(a[j]>a[i]) f2[j]=max(f2[i]+1,f2[j]);
            ans2=max(ans2,f2[j]);
        }
    }
    printf("%d\n%d",ans1,ans2);
    return 0;
}

 

相关文章

网站地图xml地图