题解：
能量值域很大，不好作为状态
因此我们可以将召唤的鸟的数目当作状态
这样我们可以轻松算出能量上限 W + j * B
然后我们现在是dp( i , j )表示到第 i 个树，召唤 j 个鸟的状态下拥有的最大能量值
然后随便转移下就好了
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define maxn 1005 4 #define maxc 10005 5 using namespace std; 6 int n,W,B,X; 7 int c[maxn],w[maxn]; 8 bool vis[maxn][maxc]; 9 ll dp[maxn][maxc]; 10 int main() 11 { 12 scanf("%d%d%d%d",&n,&W,&B,&X); 13 for(int i=1;i<=n;++i)scanf("%d",&c[i]); 14 for(int i=1;i<=n;++i)scanf("%d",&w[i]); 15 dp[0][0]=W;vis[0][0]=1; 16 int ans=0; 17 for(int i=0;i<n;++i) 18 { 19 for(int j=0;j<=10000;++j)if(vis[i][j]) 20 { 21 for(int k=0;k<=c[i+1];++k) 22 { 23 ll res=min(dp[i][j]+X,1ll*W+1ll*j*B)-1ll*k*w[i+1]; 24 if(res>=0) 25 { 26 dp[i+1][j+k]=max(dp[i+1][j+k],res); 27 vis[i+1][j+k]=1; 28 ans=max(ans,j+k); 29 } 30 } 31 } 32 } 33 printf("%d ",ans); 34 return 0; 35 }