传送门
蒟蒻净做些水题还请大佬见谅
没错这又是个一眼的分组背包。
题意简述：有n棵树，每只树上有aia_iai只鸟，第iii棵树买一只鸟要花cic_ici的钱，每买一只鸟可以奖励bbb块钱，从一棵树移动到下一棵树可以奖励xxx块钱，最初有www块钱，求买下的鸟的数量的最大值。
由于钱数很大，考虑按照选择的鸟的方案数来进行dpdpdp。
我们定义状态fi,jf_{i,j}fi,j表示走过前iii棵树买下来jjj只鸟的剩下钱数的最大值。
最后看使得fn,jf_{n,j}fn,j合法的jjj的最大值即可。
转移很简单：fi,j=max{fi−1,k−ci∗(j−k)+b∗(j−k)}f_{i,j}=max\{f_{i-1,k}-c_i*(j-k)+b*(j-k)\}fi,j=max{fi−1,k−ci∗(j−k)+b∗(j−k)}
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=1e3+5,M=1e4+5;
int n,tmp=0,a[N],up=0;
ll c[N],f[2][M],w,b,x;
int main(){
memset(f[tmp],-1,sizeof(f[tmp])),n=read(),f[tmp][0]=w=read(),b=read(),x=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1;i<=n;++i)c[i]=read();
for(ri i=1;i<=n;++i){
up+=a[i],tmp^=1,memset(f[tmp],-1,sizeof(f[tmp]));
ll sum=w;
for(ri j=0;j<=up;++j){
for(ri k=0;k<=a[i]&&k<=j;++k){
if(f[tmp^1][j-k]==-1||c[i]*k>f[tmp^1][j-k])continue;
f[tmp][j]=max(f[tmp][j],f[tmp^1][j-k]-c[i]*k);
}
if(~f[tmp][j])f[tmp][j]=min(f[tmp][j]+x,sum);
sum+=b;
}
}
for(ri i=up;~i;--i)if(~f[tmp][i])return cout<<i,0;
}