【01背包、前后缀分解】ABC441F
WanderOvO
·
·
题解
【01背包、前后缀分解】ABC441F
原题链接
简要题意
有 n 个物品，第 i 个物品的价格是 p_i，价值是 v_i，你总共有 m 元钱。
在每个物品至多买一件，且总花费不能超过 m 的情况下，问最大价值是多少。
但是这个问题太简单了，于是本题要问的是，在保证达到最大价值的情况下，每种物品是必须要买（A 类），还是买不买都可以（B 类），还是必须不能买（C 类）。
## 思路
首先需要用一个 01 背包把最大价值算出来，不妨记为 $maxv$。
然后，我们逐个去看每个物品 $i$ 是什么情况，其实可以枚举这个物品必须买和必须不买，然后快速检查前后缀的最优策略，看看总价值还是否为 $maxv$，即可判断其属于 ABC 中的哪种情况。
我们设 $pre[i][j]$ 为前 $i$ 个物品，总价格不超过 $j$ 的最大价值，$suf[i][j]$ 为第 $i$ 到第 $n$ 个物品，总价格不超过 $j$ 的最大价值。
我们枚举第 $i$ 个物品，看其情况：
- 强制买 $i$ ，则前缀和后缀的物品的总价格不能超过 $m - p[i]$，我们枚举前缀的总价格不超过 $j$，则后缀的价格不能超过 $m - p[i] - j$，这种情况下最大价值是 $mx1 = pre[i - 1][j] + v[i] + suf[i + 1][m - p[i] - j]$。
- 强制不买 $i$，则前缀和后缀的物品的总价格不能超过 $m$，我们枚举前缀的总价格不超过 $j$，则后缀的价格不能超过 $m - j$，这种情况下最大价值是 $mx2 = pre[i - 1][j] + suf[i + 1][m - j]$。
如果 $mx1 < maxv$，说明达到最大值一定不能买 $i$，是 C 类型。
否则，看 $mx2$ 和 $maxv$ 的情况。如果相等，说明可买可不买，是 B 类型，不等则说明必须买才能达到最大值，是 A 类型。
本题给了 1GB 的空间，所以 DP 数组放心开。
## 代码
```cpp
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1010;
const int M = 5e4 + 10;
const int mod = 998244353;
/*
枚举每个物品强制选或者强制不选，能否达到最优解
*/
LL pre[N][M], suf[N][M];
int p[N], v[N];
int n, m;
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> p[i] >> v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
pre[i][j] = pre[i - 1][j];
if (j >= p[i]) {
pre[i][j] = max(pre[i][j], pre[i - 1][j - p[i]] + v[i]);
}
}
}
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= m; j++) {
suf[i][j] = suf[i + 1][j];
if (j >= p[i]) {
suf[i][j] = max(suf[i][j], suf[i + 1][j - p[i]] + v[i]);
}
}
}
LL max_v = pre[n][m];
for (int i = 1; i <= n; i++) {
LL mx1 = 0;
LL r = m - p[i];
for (int j = 0; j <= r; j++) {
mx1 = max(mx1, pre[i - 1][j] + v[i] + suf[i + 1][r - j]);
}
LL mx2 = 0;
for (int j = 0; j <= m; j++) {
mx2 = max(mx2, pre[i - 1][j] + suf[i + 1][m - j]);
}
if (mx1 < max_v) {
cout << "C";
} else {
if (mx2 < max_v) {
cout << "A";
} else {
cout << "B";
}
}
}
}
int main() {
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
```