题解：P1860 新魔法药水
_TwilightSnow_
·
·
题解
赛时已严肃被创飞，于是写个题解加深一下记忆。
输出 0 能拿 10 分。
非常鬼畜的 DP。
为了方便表述，我们使用 w_i 表示药品 i 的收益，r_i，cnt_i，rs_{i,j}(1\le j \le cnt_i) 表示第 i 次魔法的成品，原料数量，原料编号。
我们想到可以设计状态 f_{i,j,k} 表示前 i 个药品使用 j 次魔法，成本为 k 的最大收益，但这貌似不太好直接转移，所以我们想到可以再算一个 c_{i, j} 表示第 i 个药品用 j 次魔法的最小成本，那么 f_{i,j,k} 的转移就很容易写了，为
再考虑一下 $c_{i,j}$ 怎么算，发现 $c_{i,j}$ 也不好直接计算出来，于是再用一次 DP 用于计算 $c_{i,j}$。设 $g_{i, j}$ 表示当前魔法配方中前 $i$ 个原料使用 $j$ 次魔法的最小成本，$g_{i,j}$ 的转移方程就非常好写了，对于每种魔法，为
$\large g_{i, j} = \min \{ g_{i-1,j-k} + c_{rs_{x,i}, k} \}$，
其中 $0 \le k \le j$，$0\le j \le t - 1$，$t$ 表示的是总魔法次数，$t - 1$ 是因为最后一次还是要用一次魔法，$x$ 表示魔法编号，这个时候的 $\large c_{rs_{x,i}, k}$ 一定是已经算出来的（想想为啥）。
然后，我们就可以得出
$\large c_{r_x, t} = g_{cnt_i, t - 1}$（$x$ 和 $t$ 的意义同上）。
还没完，我们发现各种魔法的产物有可能是相同的，所以 $c_{r_x,t}$ 还要取一个最小值才可以。
然后 $f_{i,j,k}$ 是可以压掉一维的，因为其实就是一个变种背包。对于最后的答案取一个最大值输出即可。
然后就没有然后了。
:::success[AC Code]
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, s, t) for (int i = s; i <= t; i++)
#define pre(i, s, t) for (int i = s; i >= t; i--)
const int N = 80, M = 300, K = 40, V = 1010, INF = 2e9;
int n, m, v, k, w[N], c[N][K], f[M][V], g[N][K], r[M], cnt[M], rs[M][N];
// w_i 第 i 个药品的回收价 r_i, cnt_i, rs_{i, j} 第 i 次魔法的成品，原料数，原料编号
// c_{i, j} 第 i 个药品使用 j 次魔法时的最小成本
// f_{i, j, k} 前 i 个药品用 j 次魔法花 k 元的最大收益（可以压一维）
// g_{i, j} 辅助数组，表示当前魔法配方中前 i 个原料使用 j 次魔法的最小成本
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> v >> k;
rep(i, 1, n) cin >> c[i][0] >> w[i];
rep(i, 1, n) rep(j, 1, k) c[i][j] = INF;
rep(i, 0, k) rep(j, 0, v) f[i][j] = -INF;
f[0][0] = 0;
rep(i, 1, m) {
cin >> r[i] >> cnt[i];
rep(j, 1, cnt[i]) cin >> rs[i][j];
}
rep(t, 1, k) rep(i, 1, m) {
rep(j, 1, cnt[i]) rep(s, 0, t - 1) g[j][s] = INF;
rep(j, 1, cnt[i]) rep(s, 0, t - 1) rep(ps, 0, s)
g[j][s] = min(g[j][s], g[j - 1][s - ps] + c[rs[i][j]][ps]);
c[r[i]][t] = min(c[r[i]][t], g[cnt[i]][t - 1]); // 最后还要用一次魔法！
}
rep(i, 1, n) rep(j, 0, k) rep(l, 0, j) rep(s, c[i][l], v)
f[j][s] = max(f[j][s], f[j - l][s - c[i][l]] + w[i] - c[i][l]);
int res = 0;
rep(i, 0, k) rep(j, 0, v) res = max(res, f[i][j]);
return cout << res, 0;
}
```
:::
这题的 DP 是真的复杂，给能想到的大佬磕一个了。。。