亿万先生:空中限制,标题叙述 Description

1044 拦截导弹

1998年NOIP全国联赛提升组

时间限制: 1 s

空间限制: 12八千 KB

标题等级 : 黄金 高尔德

 

 

 

 

难题叙述 Description

   
某国为了防卫敌国的导弹袭击,发展出一种导弹拦截系列。可是那种导弹拦截系统有多个毛病:即便它的率先发炮弹可以到达任意的莫大,不过之后每一发炮弹都不可以超出前一发的可观。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以唯有一套系统,因而有大概不大概挡住所有的导弹。

  

输入描述 Input Description

输入导弹依次飞来的万丈(雷达给出的高度数据是不超过30000的正整数)

  

输出描述 Output Description

输出那套系统最多能拦截多少导弹,如果要阻拦所有导弹至少要配置多少套这种导弹拦截连串。

样例输入 Sample Input

389 207 155 300 299 170 158 65 

样例输出 Sample Output

6

2

数量范围及提醒 Data Size & Hint

导弹的惊人<=贰仟0,导弹个数<=20

1044 拦截导弹

1998年NOIP全国联赛进步组

时间限制: 1 s

空间范围: 127000 KB

标题等级 : 黄金 戈尔德

 

 

 

 

题目叙述 Description

   
某国为了防御敌国的导弹袭击,发展出一种导弹拦截种类。不过那种导弹拦截系统有一个缺点:纵然它的第一发炮弹可以到达任意的可观,但是随后每一发炮弹都不能超过前一发的冲天。某天,雷达捕捉到敌国的导弹来袭。由于该连串还在试用阶段,所以唯有一套系统,因而有可能不可以阻碍所有的导弹。

  

输入描述 Input Description

输入导弹依次飞来的莫大(雷达给出的莫大数据是不当先三千0的正整数)

  

输出描述 Output Description

输出那套系统最多能拦截多少导弹,假若要堵住所有导弹至少要配置多少套那种导弹拦截系统。

样例输入 Sample Input

389 207 155 300 299 170 158 65 

样例输出 Sample Output

亿万先生:,6

2

数码范围及指示 Data Size & Hint

导弹的万丈<=30000,导弹个数<=20

分拣标签 Tags 点此进行

率先问即经典的最长不降低子体系难题,可以用一般的DP算法,也得以用便捷算法,但以此题的数据规模不须求。

  用a[x]代表原体系中第x个要素,b[x]表示长度为x的不下落子系列的尺寸,。当处理第a[x]时,可检索它可以接连到长度最大为多少的不下落子体系后(即与一些b[x]正如)。假如可以连到长度最大为maxx的不下落子连串后,则b[x]:=maxx+1。b数组被赋值的最大值就是第一问的答案。

  第二问用贪心法即可。每颗导弹来袭时,使用能挡住那颗导弹的守卫系统中上两次拦截导弹高度最低的那一套来堵住。若不设有符合这一尺度的系统,则应用一套新连串。

专注那个求的是最长不上涨子连串

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=21;
 7 const int maxn=0x7fffffff;
 8 int a[MAXN][4];
 9 int now=1;
10 int xt[MAXN];
11 int now2=0;// 系统的数量 
12 int main()
13 {
14     while(cin>>a[now][1])
15     {
16         int flag=0;
17         for(int i=1;i<=now2;i++)
18         {
19             if(xt[i]>=a[now][1])
20             {
21                 flag=1;
22                 xt[i]=a[now][1];
23                 break;
24             }
25             
26         }
27         if(flag==0)
28             {
29                 now2++;
30                 xt[now2]=maxn;
31                 xt[now2]=a[now][1];
32             }
33         a[now][2]=1;
34         a[now][3]=0;
35         now++;
36     }
37     for(int i=now-2;i>=1;i--)
38     {
39         int l=0;
40         int k=0;
41         for(int j=i+1;j<=now-1;j++)
42         {
43             if(a[j][1]<a[i][1]&&a[j][2]>l)
44             {
45                 k=j;
46                 l=a[j][2];
47             }
48         }
49         if(l>0)
50         {
51             a[i][2]=l+1;
52             a[i][3]=k;
53         }
54         
55     }
56     int ans1=0;
57     for(int i=1;i<=now-1;i++)
58     {
59         ans1=max(a[i][2],ans1);
60     }
61     printf("%d\n",ans1);
62     printf("%d",now2);
63     return 0;
64 }

 

分类标签 Tags 点此开展

首先问即经典的最长不下落子连串难题,可以用一般的DP算法,也足以用高速算法,但那一个题的多寡规模不要求。

  用a[x]代表原序列中第x个成分,b[x]意味着长度为x的不下跌子连串的长度,。当处理第a[x]时,可搜索它可以一连到长度最大为多少的不下落子种类后(即与局地b[x]正如)。假若可以连到长度最大为maxx的不下跌子体系后,则b[x]:=maxx+1。b数组被赋值的最大值就是率先问的答案。

  第二问用贪心法即可。每颗导弹来袭时,使用能拦截那颗导弹的防守系统中上一回拦截导弹中度最低的那一套来堵住。若不存在符合这一标准化的体系,则运用一套新连串。

留神那些求的是最长不上升子连串

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=21;
 7 const int maxn=0x7fffffff;
 8 int a[MAXN][4];
 9 int now=1;
10 int xt[MAXN];
11 int now2=0;// 系统的数量 
12 int main()
13 {
14     while(cin>>a[now][1])
15     {
16         int flag=0;
17         for(int i=1;i<=now2;i++)
18         {
19             if(xt[i]>=a[now][1])
20             {
21                 flag=1;
22                 xt[i]=a[now][1];
23                 break;
24             }
25             
26         }
27         if(flag==0)
28             {
29                 now2++;
30                 xt[now2]=maxn;
31                 xt[now2]=a[now][1];
32             }
33         a[now][2]=1;
34         a[now][3]=0;
35         now++;
36     }
37     for(int i=now-2;i>=1;i--)
38     {
39         int l=0;
40         int k=0;
41         for(int j=i+1;j<=now-1;j++)
42         {
43             if(a[j][1]<a[i][1]&&a[j][2]>l)
44             {
45                 k=j;
46                 l=a[j][2];
47             }
48         }
49         if(l>0)
50         {
51             a[i][2]=l+1;
52             a[i][3]=k;
53         }
54         
55     }
56     int ans1=0;
57     for(int i=1;i<=now-1;i++)
58     {
59         ans1=max(a[i][2],ans1);
60     }
61     printf("%d\n",ans1);
62     printf("%d",now2);
63     return 0;
64 }

 

相关文章

网站地图xml地图