1 条题解

  • 0
    @ 2025-10-8 16:48:43
    #include<bits/stdc++.h>
    using namespace std;
    int js_n;//僵尸的种数 
    int js_m[110];//每种僵尸花多少钱
    int js_p[110];//每种僵尸的攻击力
      
    int zw_n;//植物的行数 
    int zw_m[210000];//每行植物"最少"需要多少钱才能被击破
    int zw_p[210000];//每行植物需要多少攻击力才能被击破
      
    int M,m_p[1005]; //钱的总数、m_p[7]表示7块钱能产生的攻击力 
     
    int f[210000];//f[i]表示打掉一段植物[?,i]的总花费 
     
    int main() 
    {
        scanf("%d%d%d",&js_n,&zw_n,&M);
        for(int i=1;i<=js_n;i++)scanf("%d",&js_m[i]);
        for(int i=1;i<=js_n;i++)scanf("%d",&js_p[i]);
        for(int i=1;i<=zw_n;i++) scanf("%d",&zw_p[i]);
                                            //zw_m[i]=??
        memset(m_p,0,sizeof(m_p));m_p[0]=0;
        for(int i=1;i<=js_n;i++)
    		for(int j=js_m[i];j<=M;j++)
                m_p[j]=max( m_p[j] ,  m_p[ j-js_m[i] ] + js_p[i]  );
                      
        for(int i=1;i<=zw_n;i++)
        {
            zw_m[i]=M+1;
            for(int j=0;j<=M;j++)
                if(zw_p[i]<=m_p[j])
                {
                    zw_m[i]=j;
                    break;
                }
                /*
            int L=0,R=M,ans=M+1;
            while(L<=R)
            {
                int mid=(L+R)/2;
                if(m_p[mid]>=zw_p[i]) ans=mid,R=mid-1;
                else                    L=mid+1;
            }
            zw_m[i]=ans;
            */
        }
        /* 
        int st=-1,ed=-1,ans=0;
        f[0]=0;
        for(int i=1;i<=zw_n;i++)
        {
            if(zw_m[i]<=M)
            {
                f[i]=f[i-1]+zw_m[i];
                if(st==-1)st=i;
                ed=i;
                while(f[i]>M) f[i]-=zw_m[st],st++;
                ans=max(ans,ed-st+1);
            }
            else f[i]=0,st=ed=-1;
        }
        printf("%d\n",ans);
          */
        int sm=0,ans=0;
        deque<int> Q;
        for(int i=1;i<=zw_n;i++)
        {
            if(zw_m[i]<=M)
            {
                sm+=zw_m[i];
                Q.push_back(i);
                while(sm>M) sm-=zw_m[ Q.front() ] ,Q.pop_front();
                int tmp=Q.size();
                ans=max( ans , tmp );
            }
            else sm=0,Q.clear();
        }
        printf("%d\n",ans);
       
         
        return 0;
    } 
    • 1

    *【动态规划:状态设计DP】僵尸大战植物

    信息

    ID
    254
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    77
    已通过
    32
    上传者