评测点
题目
「题意」
植物大战僵尸这款游戏中,还有一个特别的玩法;玩家操纵僵尸进攻植物。
首先,僵尸有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 |
|