「Caioj1086」进攻策略

评测点

Caioj1086

题目

「题意」
植物大战僵尸这款游戏中,还有一个特别的玩法;玩家操纵僵尸进攻植物。
首先,僵尸有m种(每种僵尸都是无限多的),
玩家可以选择何时的僵尸来进攻。
使用第i种僵尸需要花费wi资源,可以得到pi的攻击效果。
在这里,我们认为多个僵尸总的进攻效果就是他们每个攻击效果的代数和。
地图共有n行,对于第i行,最左端有若干植物,
这些植物需要至少qi的攻击才能被全部消灭。
若一行上的植物全部被消灭,我们认为这一行被攻破。
由于资源紧张,你只有总量为k 的资源,不一定能够攻破所有行。
但僵尸博士希望攻破相邻的t行,并希望t尽量的大。你能帮他算出t的值吗?
「输入」
第一行三个非负整数:m n k
第二行m 个正整数 第i个数表示wi
第三行m个正整数 第i个数表示pi
第四行n个非负整数 第i个数表示qi
「输出」
一个正整数t
「输入样例」
3 11 39
5 2 11
3 1 7
5 3 6 10 3 2 4 200 1 1 1
「输出样例」
4
「提示」
样例说明:
打掉 10 3 2 4 这相邻的4行,需要的最小代价是16+5+4+7=32,不超过39
数据规模:
对于70%的数据 n<=1000
对于100%的数据 n<=200000,m<=100,k<=1000,所有pi ,qi<=100000000
(lzg PS:pi,qi固然大,可k是小于1000的啊!)

分析

先dp计算出i的资源能造成总共f[i]的伤害
再计算出攻下第i行的资源花费
剩下的就简单了

代码

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
33
34
35
36
37
38
39
40
41
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
int mymax(int a,int b)
{
return a>b?a:b;
}
//*******************定义*******************
int w[110],p[110],q[200010];
int f[1010],a[200010];
//*******************主函数*******************
int main()
{
int n,m,k;scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=m;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) scanf("%d",&q[i]);

for(int i=1;i<=m;i++)
for(int j=w[i];j<=k;j++)
f[j]=mymax(f[j],f[j-w[i]]+p[i]);
f[k+1]=INF;

int tou=1,ans=0,s=0;
for(int i=1;i<=n;i++)
{
int l=0,r=k,tans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(f[mid]>=q[i]) tans=mid,r=mid-1;
else l=mid+1;
}
a[i]=tans;//攻下这一行的资源花费

s+=a[i];
while(s>k and tou<=i) s-=a[tou],tou++;
ans=mymax(ans,i-tou+1);
}
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4a23.html
转载请注明出处,谢谢!