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