资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 植物大战僵尸这款游戏中，还有一个特别的玩儿法：玩家操纵僵尸进攻植物。 首先，僵尸有m种（每种僵尸都是无限多的），玩家可以选择合适的僵尸来进攻。使用第i种僵尸需要花费Wi资源，可以得到Pi的攻击效果。在这里，我们认为多个僵尸总的攻击效果就是他们每个攻击效果的代数和。 地图共有n行，对于第i行，最左端有若干植物，这些植物需要至少Qi的攻击才能被全部消灭。若一行上的植物全部被消灭，我们称这一行被攻破。 由于资源紧张，你只有总量为K的资源，不一定能够攻破所有行。但统治者希望攻破相邻的T行，并希望T尽量的大。你能帮他算出T的值吗？ 输入格式 第一行三个非负整数：m、n、K； 第二行m个正整数，第i个数表示Wi； 第三行m个正整数，第i个数表示Pi； 第四行n个非负整数，第i个数表示Qi。 输出格式 3 11 39 5 2 11 3 1 7 5 3 6 10 3 2 4 200 1 1 1 样例输入 一个满足题目要求的输入范例。 例： 2 2 1 2 3 4 样例输出 4 数据规模和约定 对于70%的数据：n<=1000
对于100%的数据：n<=200000，m<=100，K<=1000000，所有Pi、Qi<=100000000
分析：就是背包问题的扩展。
需要注意的是如果目前找到的最大击破数>=剩下的行(n-i)时可直接退出，因为后面找的都无意义。
//算法提高，进攻策略加强 #include <iostream> #include <algorithm> #define maxn 10000005 using namespace std; int ma=0,mi = maxn; int dp[maxn];//意思是对于有i个植物的一行攻破所需花的最少资源。 int w[105]; int v[105]; int A[200005]; int m,n,k; int read(){ //快速输入 int x = 0,flag =0; char ch; ch = getchar(); while(ch<'0'||ch>'9') { if(ch=='-') flag=1; ch = getchar(); } while(ch>='0'&&ch<='9') { x = (x<<1)+(x<<3); x += (ch-'0'); ch = getchar(); } if(flag) return(-x); return x; } int main() { scanf("%d %d %d",&m,&n,&k); for(int i = 1;i<=m;i++) w[i] = read(); for(int i =1;i<=m;i++) v[i] = read(); for(int i =1;i<=n;i++) { A[i]= read(); if(ma<A[i]) ma = A[i]; } dp[0] = 0; //0的情况下花费0的资源 for(int i=1;i<=m;i++) { for(int j =1;j<=ma;j++) { if(i==1) { if(j<=v[i]) dp[j] = w[i]; else dp[j] = dp[j-v[i]]+w[i]; //所需要的资源数 } else { if(j<=v[i]) dp[j] = min(dp[j],w[i]); else dp[j] = min(dp[j],dp[j-v[i]]+w[i]); } } } int t=0,c=k,num,j; for(int i=1;i<=n;i++) { c = k; num = 0; j = i; while(c&&j<=n) { if(c < dp[A[j]]) break; c -= dp[A[j]]; //printf(" 第%d行所需最少资源: %d\n",j,dp[A[j]]); num++; j++; } //cout<<"可通数量： "<<num<<endl; if(t<num) t = num; if(n-i<=num) break; //如果剩下的行数都不足的时候直接退出就行 } printf("%d\n",t); return 0; }