拦截导弹 来源:NOIP1999(提高组) 第一题
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入格式
输入数据为两行,
第一行为导弹的数目N(n<=1000)
第二行导弹依次飞来的高度,所有高度值均为不大于30000的正整数。
输出格式
1.输出只有一行是这套系统最多能拦截的导弹数和 2.要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6 2
可以先将这个问题分作两个小问题解决,第一个小问明显是要求出最长非严格下降子序列,因为它要保证每一发炮弹都不能高于前一发的高度
第二个小问则是要你求出最长严格上升子序列,这个结论就不能明显的出啦,因为一开始我也想不出来,也是看了题解才懂。
证明过程:
目标首先是要保证所有的目标都要摧毁,既然每个目标都要被摧毁,那么如果这个被摧毁的目标的后面的目标比它搞的话,摧毁这个目标
的导弹系统就不能摧毁它后面的目标了。从而,我们所需要的炮弹系统的高度必定是严格上升的序列~又因为要摧毁所有的目标,所以为最长严格
上升子序列~
ps:这道题的数据目测比较弱,第二问我用非严格上升去做也能ac。。。。。
附上ac的c++代码:
#include <cstdio>
#include <iostream> using namespace std;
const int maxn = ;
int a[maxn],inc[maxn],dece[maxn];
const int INF = 0x3f3f3f3f;
int main(){
int n;
while(~scanf("%d",&n)){
int INC = ,DEC = ;
fill(a,a + maxn,);
fill(inc,inc + maxn,);
fill(dece,dece + maxn,);
for(int i = ;i <= n;++i)
scanf("%d",&a[i]);
a[] = INF;//注意 初始化
for(int i = ;i <= n;++i){
for(int j = ;j <= i-;++j){
if(a[i] <= a[j]&&dece[i] < dece[j] + ) //非严格下降子序列
dece[i] = dece[j] + ;
}
//cout<<dece[i];
DEC = max(DEC,dece[i]);
}
//cout<<endl;
a[] = -INF;//注意重新初始化
for(int i = ;i <= n;++i){
for(int j = ;j <= i-;++j){
if(a[i] > a[j]&&inc[i] < inc[j] + ) //严格上升子序列
inc[i] = inc[j] + ;
}
//cout<<inc[i];
INC = max(INC,inc[i]);
}
//cout<<endl;
printf("%d %d\n",DEC,INC);
}
return ;
}
合唱队形 来源:NOIP2004(提高组) 第一题
题目描述
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<…<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4
思路:
设dec[i] 是以a[i] 为结尾的最长严格上升序列,inc[i] 是以a[i]开始的最长严格下降序列,所以 最终答案是 n – max(dec[i] + inc[i] – 1);
dec[i] 和inc[i] 仿照上面那道题 即可,不过注意代码细节有所不同
#include <cstdio>
#include <iostream> using namespace std;
const int maxn = ;
int a[maxn],inc[maxn],dece[maxn];
const int INF = 0x3f3f3f3f;
int main(){
int n;
while(~scanf("%d",&n)){
int INC = ,DEC = ;
fill(a,a + maxn,);
fill(inc,inc + maxn,);
fill(dece,dece + maxn,);
for(int i = ;i <= n;++i)
scanf("%d",&a[i]);
a[] = -INF;//注意 初始化
for(int i = ;i <= n;++i){
for(int j = ;j <= i-;++j){
if(a[i] > a[j]&&dece[i] < dece[j] + ) //
dece[i] = dece[j] + ;
}
}
a[n+] = -INF;//注意重新初始化
for(int i = n;i >= ;--i){
for(int j = n+;j >= i + ;--j){
if(a[i] > a[j]&&inc[i] < inc[j] + ) //
inc[i] = inc[j] + ;
}
}
int ans = ;
for(int i = ;i <= n;i++){
ans = max(ans,dece[i] + inc[i]);
}
printf("%d\n",n - ans + );
}
return ;
}