【2014广州市选day1】JZOJ2020年9月12日提高B组T2 导弹拦截
题目
Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统 V1.0。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够达到任意的高度,但是以后每一发炮弹都不能高于前一发的高度,这样会大大降低导弹的拦截率。
经过技术人员的苦心改良,导弹拦截系统升级为 V2.0,使得这个拦截系统在拦截过程中,有若干次机会提升到任意高度,虽然次数有限,但是已经算很大的改进了。
某天,雷达捕捉到敌国的导弹来袭,导弹 V2.0拦截系统接受考验的时刻开始来临了。
Input
第一行为整数N (0<=N<=20),M(1<=M<=50),N代表导弹拦截系统在拦截过程中,可以提升到任意高度的次数;M代表需要拦截的导弹的数目。N、M两个整数用空格隔开。
第二行为M个正整数,每个整数间使用若干空格隔开,分别表示导弹依次飞来的高度,雷达给出高度数据是不大于1000的正整数。
Output
输出一个正整数,代表该导弹拦截系统最多可以拦截的导弹数目。
Sample Input
1 7
300 250 275 252 200 138 245
Sample Output
6
题解
题意
给出一个导弹拦截系统
第一发可以打到任意高度,但之后每一次都要低于前一次
有(n)次机会可以上升到任意高度
问在(m)个导弹里最多可以拦截多少个
分析
DP模板题导弹拦截升级版
一样是采取DP的方式
只不过有些不同
设(f[i][j])表示当前是第(i)个导弹,用了(j)次提升高度
那么转移显然
- 当可以直接打到时 (f[i][j]=max(f[i][j],f[i-1][j]+1))
- 当可以是使用提升高度时 (f[i][j+1]=max(f[i][j+1],f[i-1][j]+1))
注意的是(f[i][j])的初值是(max(f[i-1][j]))
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[55],f[55][25];
int read()
{
int res=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
return res;
}
int main()
{
freopen("missile.in","r",stdin);
freopen("missile.out","w",stdout);
m=read();n=read();
for (int i=1;i<=n;++i)
a[i]=read();
f[1][0]=f[1][1]=1;
for (int i=2;i<=n;++i)
for (int j=0;j<=min(i,m);++j)
{
f[i][j]=max(f[i][j],f[i-1][j]);
if (a[i]<=a[i-1])
{
f[i][j]=max(f[i-1][j]+1,f[i][j]);
if (j+1<=m) f[i][j+1]=max(f[i-1][j]+1,f[i][j+1]);
}
else if (j+1<=m) f[i][j+1]=max(f[i-1][j]+1,f[i][j+1]);
}
for (int i=1;i<=n;++i)
for (int j=0;j<=m;++j)
ans=max(ans,f[i][j]);
printf("%d
",ans);
fclose(stdin);fclose(stdout);
return 0;
}