哎……做了几个小时最后还是没能想到怼大佬的合法性到底怎么搞。写暴力爆搜感觉复杂度爆炸就没敢写 bfs / dfs 一类，后来发现在种种的约束条件下（远小于所给的 \(n, m\)）复杂度完全是可以承受的。不过就算想到了这一步谅我也想不出用单调栈来搞两次的组合吧。
这题最开始就应该发现：扣血和回血完全是可以分开的两个操作。为什么这个点很容易发现呢：1.扣血的多少与时间是无关的。2.本题要求活着（血量 >= 0）而非最大化血量。所以第一步显然应当 dp 出在保证活着的前提下最多能够空出多少天来对付 ‘大佬’。
然后来考虑，假设我们最多拥有 \(D\) 天来攻击，是否存在一种攻击方案使得'大佬'的血量正好为0。预处理出 \(g[k][d]\) 代表 \(d\) 次操作，是否可能对'大佬'产生 \(k\) 点伤害。（这里用Map来存储，并注意这里的方案只考虑怼一次）。然后我们假设存在一种合法的方案怼大佬两次使得大佬血量正好为0，第一次扣血 \(f1\) 点，耗费时间为 \(d1\) 天，第二次扣血 \(f2\) 点，耗费时间为 \(d2\) 天。他们之间该满足什么样的关系式呢？ （设大佬血量为 \(M\)）
\(M >= f1 + f2\)
\(M - f1 - f2 <= D - d1 - d2\)
其中（1）式表示不能减为负数，（2）式表示没有减完的血量可以通过还嘴来减掉。之后将（2）式移项（构造常量与非常量之间的不等式以方便检查）
\(D >= M - f1 - f2 + d1 + d2\)
然后我们选择枚举这两次怼大佬之间的其中一个，则不确定的项即为 \(d2 - f2\) ，因为要求右边的小，所以求这个的最小值之后判断就好了。又因为有之前（1）式的约束，我们在固定了 \(f1\) 后如果能够将 \(f\) 从小到大排序，即可方便判断何时一定不满足（单调递增）。
#include <bits/stdc++.h>
using namespace std;
#define maxn 110
#define ll long long
#define INF 990000000
int n, m, mc, a[maxn], w[maxn];
int ans, maxx, top, B[maxn];
int mark[maxn], f[maxn][maxn];
pair <int, int> S[];
map <int, int> Map[maxn]; struct node
{
int num, v, lev;
}; int read()
{
int x = , k = ;
char c;
c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} void upmax(int &x, int y) { x = x > y ? x : y; } void DP()
{
for(int i = ; i <= n; i ++)
for(int j = ; j <= mc - a[i]; j ++)
{
upmax(f[i][min(mc, j + w[i])], f[i - ][j + a[i]]); // add blood
upmax(f[i][j], f[i - ][j + a[i]] + ); // do nothing
ans = max(f[i][j], ans);
}
} void BFS(int tot)
{
queue <node> q; q.push((node) {, , });
while(!q.empty())
{
node x = q.front(); q.pop();
if(x.num < tot)
{
q.push((node) {x.num + , x.v, x.lev + });
if(x.lev > && x.v < maxx / x.lev && !Map[x.lev][x.v * x.lev])
{
node y = (node) { x.num + , x.v * x.lev, x.lev};
Map[x.lev][x.v * x.lev] = ;
S[++ top] = make_pair(y.v, y.num); q.push(y);
}
}
}
} int main()
{
n = read(), m = read(), mc = read();
for(int i = ; i <= n; i ++) a[i] = read();
for(int i = ; i <= n; i ++) w[i] = read();
for(int i = ; i <= m; i ++) B[i] = read(), maxx = max(maxx, B[i]);
memset(f, , sizeof(f)); f[][mc] = ; DP();
BFS(ans); sort(S + , S + top + );
for(int i = ; i <= m; i ++)
{
int t = B[i], fans = , fmin = INF;
if(t < ans) { printf("1\n"); continue; }
for(int j = top, k = ; j; j --)
{
while(k <= top && S[k].first + S[j].first <= t)
fmin = min(fmin, S[k].second - S[k].first), k ++;
if(fmin + t - S[j].first + S[j].second <= ans) { fans = ; break; }
if(S[j].first <= t && S[j].second + t - S[j].first <= ans) { fans = ; break; }
}
printf("%d\n", fans);
}
return ;
}