题解：CF922E Birds

· · 题解

Birds

逆天冲刺 NOIP 题单可做题之二。

首先看数据范围，肯定不能用魔法上限和魔法做 \text{dp} 的决策。

考虑 f_{i,j} 表示在走到第 i 棵树，买了 j 只鸟的时候的最大魔力数。

然后很明显的我们存在一个转移方程。

f_{i,j}=\max\{f_{i-1,j-k}+\text X-\text{cost}_i\times k\}

因为存在魔力上限和魔力下限，因此 f_{i,j}>0 且 f_{i,j}<\text W+\text{cost}_i \times j。

这里有一个边界，f_{0,0}=\text W，因为此时没有选择任何一只鸟而且没有走任何一棵树。

最后只要倒序枚举去判断是否存在即可，这样就能求出最大的鸟数。

代码

namespace solve{
    inline int read(){
        int s=0,w=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
        return s*w;
    }
    inline void write(const int x){
        if(x>=10) write(x/10);
        putchar(x%10+'0');
    }
    inline void print(const int x,string s){
        if(x<0) putchar('-');
        write(x<0?-x:x);
        int len=s.size();
        for_(i,0,len-1) putchar(s[i]);        
    }
    int c[1005],C[1005],sum[1005],f[1005][10005];
    inline void In(){
        int n=read(),W=read(),B=read(),X=read();
        for_(i,1,n){
            c[i]=read();
        }
        for_(i,1,n){
            C[i]=read();
        }
        for_(i,1,n){
            sum[i]=sum[i-1]+c[i];
        }
        memset(f,-1,sizeof(f));
        f[0][0]=W;
        for_(i,1,n){
            for_(j,0,sum[i]){
                int len=min(j,c[i]);
                for_(k,0,len){
                    if(f[i-1][j-k]-C[i]*k>=0){
                        if(f[i-1][j-k]!=-1){
                            f[i][j]=max(f[i-1][j-k]+X-C[i]*k,f[i][j]);
                        }
                    }
                }
                if(f[i][j]>W+B*j) f[i][j]=W+B*j;
            }
        }
        _for(i,sum[n],1){
            if(f[n][i]!=-1){
                print(i,"\n");
                return;
            }
        }
        print(0,"\n");
    }
}