dp豪题

Luogu 3188

给你 $n$ 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 $W$，且总价值最大，并输出最大的总价值。

$1\le n \le 100$，$1\le W,w_i,v_i \le 2^{30}$。
保证每个 $w_i$ 能写成 $a \times 2^b\space (a,b \in \mathbb N)$ 的形式，$a \leq 10$ , $b \leq 30$，且答案不超过 $2^{30}$。

---

我擦，背包牛逼题。

注意到这个 $w_i=a \times 2^b$ 的情况里面 $a$ 很小，能启示我们按照 $b$ 去分组，组内进行背包。

设 $g_{i, j}$ 表示 $i$ 这一组里面的 $a$ 之和为 $j$ 的时候价值的最大值，这里我们把 $a$ 当成了物体的体积。转移是简单的。

但是还有一个问题就是：如何把这些信息合并，让它们放到 $W$ 里面。设 $f_{i, j}$ 表示考虑到第 $i$ 组，当前选择的体积能够表示成 $j\times 2^{i-1}+X$，其中 $X$ 满足小于等于 $W$ 的 $0\sim i-1$ 位组成的二进制数。

转移考虑枚举当前这一组选了 $p$ 个，那么剩下了 $(j-p)\times 2^{i-1}$ 个，放到前面那组就是 $2\times (j-p)\times 2^{i-2}$ 个，还要考虑上新增加的 $W$ 的第 $i-1$ 位，因为 $(j-p)\times 2$ 已经贡献到前面的位了。所以有转移：

$$f_{i, j}=\max(f_{i-1, (j-p)\times 2+W_{i-1}}+g_{i-1, p})$$

Luogu 10303

Yazid 今天要听 $n$ 个人做报告，方便起见，我们把这些人从 $1$ 至 $n$ 编号。Yazid 有一个兴奋度，初始为 $s$，这个值会随着报告的进行而改变。

第 $i$ 个人（$1\leq i\leq n$）的报告可以用三个数 $a_i,b_i,c_i$ 来描述，这表示假设听他的报告前，Yazid 的兴奋度为 $x$，那么听完他的报告后，Yazid 的兴奋度将会变成 $a\lvert x\rvert+bx+c$。

帮助 Yazid 安排确定所有人的报告顺序，使得 Yazid 在所有人报告完后兴奋度最大。

$n\leq 15$，保证 $a,b,c,s$ 的绝对值均不超过 $15$。

---

这个题可以很好的帮助思考最优子结构的本质。一开始想的做法肯定就是记 $f_S$ 为听了一些人的报告之后的最大值，转移显然。但是我们发现这个东西并不单调啊，小于 $0$ 的可能会逆袭啊。

先来考虑 $c=0$ 的情况，那么函数就变成了一个 $x<0$ 的时候 $y=(b-a)x$，$x>0$ 的时候 $y=(a+b)x$，我们就得维护 $<0$ 的最大最小值，$>0$ 的最大最小值，转移就完了。

但是 $c$ 不等于 $0$ 的，那么 $<0$ 的也有可能去 $+c$ 逆袭。那么我们就维护靠近 $[-c, c]$ 这段区间的值，但是要维护这个又要维护另一个东西……那我们大不了维护 $[-\sum c, \sum c]$ 这段区间所有的值，然后转移只需要这么那么一下就可。

【UR #1】外星人

给定初始值 $x$，$n$ 个正整数 $a_i$，求有多少个排列 $p_i$ 满足按照 $1\sim n$ 执行 $x\leftarrow x \bmod a_{p_i}$ 之后得到的 $x$ 最大。

$x\le 1000, x, a_i\le 5000$。

---

考虑如果你在 $x$ 后面放一个 $a_k$，是不是从 $x\bmod a_k \sim x$ 这些值的 $a$ 接下来就随便放了。

那么我们就记 $f_x$ 为从 $x$ 开始，只使用 $a_i\le x$ 的值，最终得到的最大值和方案数，转移就枚举下一位放啥，从 $f_{x\bmod j}$ 转移过来，方案数要乘个系数，懒得写了。