https://cn.vjudge.net/problem/1365218/origin
题意 一条直线上有n棵树 每棵树上有ci只鸟 在一棵树底下召唤一只鸟的魔法代价是costi 每召唤一只鸟，魔法上限会增加B 从一棵树走到另一棵树，会增加魔法X 一开始的魔法和魔法上限都是W 问最多能够召唤的鸟的个数
显然这是一道DP题
用dp[i][j]来表示到j这个树下选到j只鸟可以获得的最大能量值
很容易得出dp状态转移方程dp[i][j] = max(dp[i][j],dp[i][j - 1] - cost,dp[i - 1][j - 1] - cost);
由于每棵树上的鸟数量有限制，需要多一重大小为c的循环，但是因为∑c为1e3，三重循环的时间复杂度事实上仅为O(n * sum(c)）可以接受
初始状态是dp[i][0] = W; 其他的状态为-1表示无法到达
进而可以考虑到每棵树事实上是一个多重背包，在dp的过程中考虑二进制优化，以及将dp开成滚动数组来优化空间
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = 1e3 + ;
const int maxm = 1e4 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,tmp,K;
LL W,B,X;
LL dp[][maxm];
PIL b[maxn];
vector<PIL>P;
int C[maxn];
int main()
{
scanf("%d%lld%lld%lld",&N,&W,&B,&X);
int sum = ;
Mem(dp,-);
For(i,,N) Sca(C[i]);
For(i,,N){
Mem(dp[i & ],-);
dp[i & ][] = W;
int c = C[i]; LL cost;
scanf("%lld",&cost);
P.clear();
P.pb(mp(,));
sum += c;
//cout << sum <<endl;
tmp = ;
for(int j = ; j <= c; j <<= ){
P.pb(mp(j,cost * j));
c -= j;
}
if(c) P.pb(mp(c,cost * c));
for(int k = ; k < P.size(); k ++){
PIL u = P[k];
for(int j = sum;j >= u.fi ; j--){
if(dp[i & ][j - u.fi] >= u.se) dp[i & ][j] = max(dp[i & ][j],dp[i & ][j - u.fi] - u.se);
if(dp[i - & ][j - u.fi] == -) continue;
LL t = min(dp[i - & ][j - u.fi] + X,W + B * (j - u.fi));
if(t >= u.se) dp[i & ][j] = max(dp[i & ][j],t - u.se);
}
}
}
int ans;
_For(i,sum,){
if(dp[N & ][i] != -){
ans = i;
break;
}
}
Pri(ans);
return ;
}