导弹拦截问题系列（dp）-白红宇

导弹拦截问题系列（dp）

阅读量：4207 次

发布时间：2019-05-26

本文共 3129 字，大约阅读时间需要 10 分钟。

导弹问题1

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹?该导弹数量不超过100个

样例：

INPUT

389 207 155 300 299 170 158 65

OUTPUT

6（最多能拦截的导弹数）

样例输入

389 207 155 300 299 170 158 65

样例输出

代码

C++
              
           1 
           2 
           3 
           4 
           5 
           6 
           7 
           8 
           9 
           10 
           11 
           12 
           13 
           14 
           15 
           16 
           17 
           18 
           19 
           20 
           21 
           22 
           23 
           24 
        
#include<iostream> 
using
 
namespace
 
std
;
 
int
 
n
=
2
,
h
[
101
]
=
{ 
0
}
,
a
[
101
]
=
{ 
0
}
,
best
=
1
,
maxlong
;
 
int
 
main
(
)
 
{ 
    
    
a
[
1
]
=
1
;
 
    
while
(
cin
>>
h
[
n
]
)
 
        
n
++
;
 
    
n
--
;
 
    
for
 
(
int
 
i
=
2
;
i
<=
n
;
i
++
)
 
    
{ 
 
        
maxlong
=
1
;
 
        
for
 
(
int
 
j
=
1
;
j
<=
i
-
1
;
j
++
)
 
        
{ 
 
            
if
 
(
h
[
i
]
<
h
[
j
]
)
 
                
if
 
(
a
[
j
]
+
1
>
maxlong
)
 
maxlong
=
a
[
j
]
+
1
;
 
            
a
[
i
]
=
maxlong
;
 
        
}
 
    
}
 
    
for
 
(
int
 
i
=
1
;
i
<=
n
;
i
++
)
 
        
if
 
(
a
[
i
]
>
best
)
 
best
=
a
[
i
]
;
 
    
cout
<<
best
;
 
    
return
 
0
;
}
       
     

导弹问题2

题目描述

　　某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），该导弹数量不超过100个，计算这套系统最多能拦截多少导弹，分别是哪些导弹，本题保证所给的数据最优解只有一组

样例：
INPUT
389 207 155 300 299 170 158 65
OUTPUT
6（最多能拦截的导弹数）
389 300 299 170 158 65

样例输入

389 207 155 300 299 170 158 65

样例输出

389 300 299 170 158 65

代码

C++
              
           1 
           2 
           3 
           4 
           5 
           6 
           7 
           8 
           9 
           10 
           11 
           12 
           13 
           14 
           15 
           16 
           17 
           18 
           19 
           20 
           21 
           22 
           23 
           24 
           25 
           26 
           27 
           28 
           29 
           30 
           31 
           32 
        
#include<iostream>
using
 
namespace
 
std
;
int
 
main
(
)
{ 
    
int
 
n
=
1
,
sum
=
0
,
Max
=
0
,
s
;
    
int
 
i
,
j
;
    
int
 
a
[
101
]
,
b
[
101
]
;
    
int
 
f
[
101
]
;
    
while
(
cin
>>
a
[
n
]
)
{ 
n
++
;
}
    
n
--
;
        
for
(
i
=
1
;
i
<=
n
;
i
++
)
 
    
{ 
        
f
[
i
]
=
1
;
    
}
    
for
(
i
=
2
;
i
<=
n
;
i
++
)
    
{ 
        
for
(
j
=
1
;
j
<
i
;
j
++
)
        
{ 
        
if
(
a
[
i
]
<
a
[
j
]
)
f
[
i
]
=
max
(
f
[
i
]
,
f
[
j
]
+
1
)
;
        
}
        
if
(
f
[
i
]
>
Max
)
 
{ 
Max
=
f
[
i
]
;
 
b
[
1
]
=
a
[
i
]
;
}
    
}
   
    
cout
<<
Max
<<
endl
;
    
s
=
Max
-
1
;
    
for
(
i
=
n
,
j
=
2
;
i
>
0
;
i
--
)
    
{ 
        
if
(
f
[
i
]
==
s
)
 
{ 
b
[
j
]
=
a
[
i
]
;
j
++
;
s
--
;
}
}
    
for
(
i
=
Max
;
i
>
0
;
i
--
)
    
{ 
cout
<<
b
[
i
]
;
if
(
i
!=
1
)
cout
<<
' '
;
 
}
    
return
 
0
;
}
       
     

导弹问题3

题目描述

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），该导弹数量不超过100个计算这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入

389 207 155 300 299 170 158 65

样例输出

6（最多能拦截的导弹数）

2（要拦截所有导弹最少要配备的系统数）

C++
              
           1 
           2 
           3 
           4 
           5 
           6 
           7 
           8 
           9 
           10 
           11 
           12 
           13 
           14 
           15 
           16 
           17 
           18 
           19 
           20 
           21 
           22 
           23 
           24 
           25 
           26 
           27 
           28 
           29 
           30 
           31 
        
#include<iostream>
using
 
namespace
 
std
;
int
 
main
(
)
{ 
    
int
 
n
=
1
,
q
=
1
,
i
,
j
,
s
,
Max
,
h
[
101
]
,
a
[
101
]
,
f
[
100
]
;
    
while
(
cin
>>
h
[
n
]
)
n
++
;
 
n
--
;
    
for
(
i
=
1
;
i
<=
n
;
i
++
)
 
f
[
i
]
=
1
;
    
for
(
i
=
2
;
i
<=
n
;
i
++
)
    
{ 
        
for
(
j
=
1
;
j
<
i
;
j
++
)
        
{ 
        
if
(
h
[
i
]
<
h
[
j
]
)
f
[
i
]
=
max
(
f
[
i
]
,
f
[
j
]
+
1
)
;
        
}
        
if
(
f
[
i
]
>
Max
)
 
{ 
Max
=
f
[
i
]
;
}
    
}
    
for
(
i
=
1
,
s
=
30001
;
i
<=
n
;
i
++
)
    
{ 
     
for
(
j
=
1
;
;
j
++
)
     
{ 
         
if
(
a
[
j
]
==
0
)
break
;
         
if
(
a
[
j
]
>
h
[
i
]
)
s
=
min
(
s
,
a
[
j
]
)
;
     
}
     
if
(
s
==
30001
)
{ 
a
[
q
]
=
h
[
i
]
;
q
++
;
}
     
else
 
for
(
j
=
1
;
j
<=
n
;
j
++
)
     
{ 
        
if
(
a
[
j
]
==
s
)
{ 
a
[
j
]
=
h
[
i
]
;
break
;
}
     
}
    
}
    
cout
<<
Max
<<
endl
<<
q
;
    
return
 
0
;
}
       
     

转载地址：http://beali.baihongyu.com/

你可能感兴趣的文章