题目描述
Solution
我们令 $f[i][j]$ 表示前 $i$ 棵树，我们召唤了 $j$ 只鸟所剩下的最大法力值
转移大概是这样
1
2
3
4
5
6
7
8
| for (int i = 1; i <= n; ++i)
for (int j = 0; j <= s[i - 1]; ++j) {
if (f[i][j] == -1) continue;
for (int k = 0; k <= a[i]; ++k) {
if (f[i][j] < k * c[i]) break;
f[i + 1][j + k] = max(f[i + 1][j + k], min(w + (j + k) * b, f[i][j] - k * c[i] + x));
}
}
|
这个东西看起来复杂度是 $O(n(\sum a_i)^2)$ 的
但其实并不是，我们考虑对于 $\sum a_i$ 中的任意两个数 $(x,y)$，他们仅会被算一次
所以实际上的复杂度是 $O(n\sum a_i+(\sum a_i)^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <iostream>
#include <cstdio>
#define maxn 1010
#define maxm 10010
#define ll long long
using namespace std;
int n;
ll w, b, x, c[maxn];
int a[maxn], s[maxn];
ll f[maxn][maxm];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> w >> b >> x;
for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
for (int i = 1; i <= n; ++i) cin >> c[i];
fill(f[0], f[0] + maxn * maxm, -1); f[1][0] = w;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= s[i - 1]; ++j) {
if (f[i][j] == -1) continue;
for (int k = 0; k <= a[i]; ++k) {
if (f[i][j] < k * c[i]) break;
f[i + 1][j + k] = max(f[i + 1][j + k], min(w + (j + k) * b, f[i][j] - k * c[i] + x));
}
}
int ans = 0;
for (int i = s[n]; i; --i)
if (~f[n + 1][i]) { ans = i; break; }
cout << ans << "\n";
return 0;
}
|