「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行的资源花费
剩下的就简单了

代码

#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);
}