冯梓轩集训总结2
geven
·
·
个人记录
背包总结
模板
### 多重背包
问题描述：给定物品数量 $n$ 和背包容量 $m$，对于第 $i$ 个物品，他的体积为 $w_i$，价值为 $v_i$，件数为 $s_i$。求最终能获得的最大价值。
#### 朴素
显然，设 $f_{i,j}$ 表示前 $i$ 个物品中，放入体积和为 $j$ 的物品能得到的最大价值。
方程很好推：
$$
f_{i,j} = \max_{0 \leq k \leq \min \{ s_i,\lfloor \frac{j}{w_i} \rfloor \}} \{ f_{i,j}, f_{i-1,j-k \times w_i} + k \times v_i \}
$$
这样做的时间复杂度为 $O(n m \sum\limits_{i=1}^{n} s_i)$，数据稍微强一点就会超时。
#### 二进制优化
显然，每一个数都可以被唯一的二进制数表示。根据这一性质，我们把一个物品按照其二进制表示拆成多个物品，最终跑个 $0/1$ 背包即可。时间复杂度 $O(nm \sum\limits_{i=1}^{n} \log_2(s_i))$。
但是在某些毒瘤数据面前，这样的时间复杂度还不足以通过。
#### 单调队列优化
观察到一个性质：对于容量 $j$，物品 $i$，$j - p \times w_i \equiv j - q \times w_i \pmod{w_i}$。
所以状态转移中只会用到与其容量关于 $w_i$ 同余的状态，可以按照 $\bmod w_i$ 的余数进行分类：
$$
\begin{aligned}
& 0,w_i,2w_i,3w_i,\cdots,k_0w_i
\\
& 1,1+w_i,1+2w_i,1+3w_i,\cdots,1+k_1w_i
\\
& \cdots
\\
& x,x+w_i,x+2w_i,x+3w_i,\cdots,x+k_xw_i
\end{aligned}
$$
其中容量均小于等于 $m$。
根据组别改写状态转移方程，可得：
$$
\begin{aligned}
f_{i,x} &= \max \{ f_{i-1,x} + 0v_i \}
\\
f_{i,x+w_i} &= \max \{ f_{i-1,x} + 1v_i, f_{i-1,x+w_i} + 0v_i \}
\\
f_{i,x+2w_i} &= \max \{ f_{i-1,x} + 2v_i, f_{i-1,x+w_i} + 1v_i, f_{i-1,x+2w_i} + 0v_i \}
\\
& \cdots
\\
f_{i,x+kw_i} &= \max \{ f_{i-1,x} + kv_i, f_{i-1,x+w_i} + (k-1)v_i, f_{i-1,x+2w_i} + (k-2)v_i, \cdots, f_{i-1,x+kw_i} + 0v_i \}
\end{aligned}
$$
但是这样的转移中，$v_i$ 的系数一直在变化，所以考虑将式子变形。
将 $\max$ 中的 $kv_i$ 提出，得：
$$
\begin{aligned}
f_{i,x} &= \max \{ f_{i-1,x} + 0v_i \} - 0v_i
\\
f_{i,x+w_i} &= \max \{ f_{i-1,x} + 0v_i, f_{i-1,x+w_i} - 1v_i \} + 1v_i
\\
f_{i,x+2w_i} &= \max \{ f_{i-1,x} + 0v_i, f_{i-1,x+w_i} - 1v_i, f_{i-1,x+2w_i} - 2v_i \} + 2v_i
\\
& \cdots
\\
f_{i,x+kw_i} &= \max \{ f_{i-1,x} + 0v_i, f_{i-1,x+w_i} - 1v_i, f_{i-1,x+2w_i} - 2v_i, \cdots, f_{i-1,x+kw_i} - kv_i \} + kv_i
\end{aligned}
$$
可以发现， 每个转移中 $v_i$ 的系数只和状态被枚举到的时间点有关，而一旦出现了一个更优的状态，之前的状态就不会作为转移来处理，且每个状态都最多转移到其后第 $s_i$ 个时间点所枚举的状态。这就相当于是一个__滑动窗口__，可以考虑用单调队列优化 DP 求解。
代码如下：
```cpp
for(int i=1,w,v,s;i<=n;i++){
scanf("%d%d%d",&w,&v,&s);
if(w>m) continue;
for(int j=0;j<w;j++){
head=0,tail=-1;
for(int k=0;j+k*w<=m;k++){
if(head<=tail&&q[head]+s<k) head++;//一个物品最多用s次
while(head<=tail&&pre[q[tail]*w+j]-q[tail]*v<=pre[k*w+j]-k*v) tail--;
q[++tail]=k;
dp[k*w+j]=pre[q[head]*w+j]+(k-q[head])*v;
}
}
for(int j=0;j<=m;j++) pre[j]=dp[j];
}
```
这里枚举物品 $O(n)$，枚举余数 $O(w)$。由于单调队列总时间复杂度与循环次数相同，遂枚举系数 $O(\lfloor \frac{m}{w} \rfloor)$。
总时间复杂度为 $O(\sum\limits_{i=1}^{n}w \lfloor \frac{m}{w} \rfloor) \approx O(nm)$，非常优秀。
### 容量存在性
有 $n$ 个物品，每个物品有一个体积 $w_i$。求对于每一个容量 $i \leq m$ 是否存在放置方案使得容量 $i$ 被放满。
设 $f_i$ 表示是否能装满容量 $i$，方程显然为：
$$
f_i \mid= f_{i-w}
$$
时间复杂度为 $O(nm)$。由于存储的信息都是 $0/1$，可以考虑用 bitset 优化。写法为：
$$
f \mid= f \ll x
$$
这时时间复杂度为 $O(\frac{nm}{w})$，已经很优秀了。
### 不选某个物品
求不选物品 $i$，体积为 $j$ 的方案数。
依旧设 $f_j$ 表示容量为 $j$ 的方案数，很容易可以得到一个答案：
$$
ans = f_j - f_{j-w_i}
$$
但是这样是不对的，因为在之前的状态 $f_{j-w_i}$ 中，可能就已经考虑到了选取 $w_i$ 的情况，而再加一个 $w_i$，相当于出现了两个 $w_i$，而这与题意中每个物品只有一个的定义不符，所以我们需要考虑不选物品 $i$ 的情况。
设 $g_j$ 表示不选物品 $i$，容量为 $j$ 的方案数，则可得：
$$
g_j =
\left\{
\begin{matrix}
f_j \thinspace (0 \leq j < w_i)
\\
f_j - g_{j-w_i} \thinspace (\operatorname{otherwise})
\end{matrix}
\right.
$$
由于 $g_{j-w_i}$ 没有考虑物品 $i$，所以 $g_{j-w_i+w_i} = g_j$ 就只考虑了加入一个物品 $i$ 的情况，是正确的转移。
## 例题
### 21点
显然，以不同卡片结尾都是不同的方案，而最后选取的卡片数、卡片总和也会影响方案，所以都要考虑。
设 $f_{i,j}$ 表示选取 $i$ 张卡片，它们的点数总和为 $j$ 的方案数。
对于一个卡片 $i$，点数为 $a_i$，状态转移为：
$$
f_{j,k} = f_{j,k} + f_{j-1,k-a_i} \times \frac{j}{n-j+1}
$$
其中 $f_{j-1,k-a_i}$ 表示选取物品 $i$ 之前的选取情况，乘上 $\frac{1}{n-j+1}$ 是因为选取 $j-1$ 张牌后剩下 $n-j+1$ 张卡片，而每张卡片被选取的概率是相同的。乘上 $j$ 是因为在这 $j$ 张卡片中卡片 $i$ 被选取的时间点可以任意。
接下来枚举最后一张选取的卡片 $i$。由于每种卡片只有一张，所以在选取卡片 $i$ 之前是不能选卡片 $i$ 的，需要记录不选卡片 $i$ 的情况。
设 $g_{j,k}$ 表示不选第 $i$ 张卡片，选取 $j$ 张卡片，点数总和为 $k$ 的方案数。类比模板，可得：
$$
g_{j,k} =
\left \{
\begin{matrix}
f_{j,k} \thinspace (0 \leq k < a_i)
\\
f_{j,k} - g_{j-1,k-a_i} \times \frac{j}{n-j+1} \thinspace (\operatorname{otherwise})
\end{matrix}
\right.
$$
由于是选取最后一张牌之后获胜，而获胜条件是总和大于 $l$，小于 $r$，所以之前的点数总和 $k$ 要满足的条件是：$0 \leq k \leq l,l < k+a_i < r$。
再枚举一下上一步选取的卡片数 $j$，可得答案为：
$$
ans = \sum\limits_{j=0}^{n-1} \sum\limits_{k=0}^{l} \frac{g_{j,k}}{n-j} [l < k+a_i < r]
$$
这里不乘上 $j+1$ 的原因是：__第 $i$ 张牌被选的顺序已经确定__。
### [模拟赛20221105] 计数
类比上一个题，有两个玩家，那就开两个 $f$ 数组记录方案数。按照相同的方式枚举选取的阶段、gvz 选的最后一张牌、zzh 选取的总和与 gvz 上一步选取的总和，再按相同方式统计答案。
注意：
$1.$ 由于选取的是个排列，在选取结束时还会剩下一些牌，这些牌可以用任意的顺序选取，所以要乘上一个阶乘。
$2.$ 如果直接枚举 gvz 上一步选取的总和，总时间复杂度为 $O(n^2m^2)$，超时。由于总和的范围是一段连续区间，遂可以考虑用前缀和优化，时间复杂度为 $O(n^2m)$。
### 拔河比赛
可以考虑将二班同学的力量值取反，问题转化为：在序列中选取一些数，使得其体积和为 $0$ 且价值和最大。
但是直接枚举的上下界过大，空间就会爆炸。考虑将序列__随机打乱__，这样可以使得体积和分布较为均匀，且__体积的前缀和不会很大__。之后就是一个 $0/1$ 背包。
### 背包与根号分治
#### 小Y的背包计数问题
朴素转移时间复杂度为 $O(n^2)$，不足以通过本题。考虑根号分治。
对于一个物品 $i$，其体积也为 $i$：
$(1) ~ i \leq \sqrt{n}
此时直接跑多重背包即可，时间复杂度为 O(n \sqrt{n})。
(2) ~ i > \sqrt{n}
由于背包容量为 n，所以对于一个 i > \sqrt{n}，其最多选取的个数为 x < \sqrt{n} ，所以 x < i，可以将其转化为完全背包求解。
但是朴素的完全背包时间复杂度依然是 O(n^2)。考虑类比自然数拆分问题进行求解。
设 f_{i,j} 表示在体积大于 \sqrt{n} 的物品中选取 i 个物品，其体积和为 j 的方案数。
状态转移为：
f_{i,j} =
\left \{
\begin{matrix}
f_{i,j-i} \thinspace (i \leq j \leq \sqrt{n})
\\
f_{i,j-i} + f_{i-1,j-(\sqrt{n}+1)} \thinspace (\operatorname{otherwise})
\end{matrix}
\right.
对应的转移为：
$2.$ 添加一个数 $\sqrt{n}+1$。
这样做转移，统计到的方案不重不漏，且时间复杂度为 $O(n \sqrt{n})$。
最后的总时间复杂度为 $O(n \sqrt{n})$。
#### 无平方数
感觉是做过的最好的一道背包题。
对于 $n \leq 50$，显然有一种做法：
设 $f_{i,s}$ 表示选了 $i$ 个数，其中这几个数的乘积的质因数包含情况为 $s$。那么我们只需要每次转移时枚举一个物品，再枚举一个状态 $f_{i,s}$，只要这个数的质因数包含情况和 $s$ 没有交集，就考虑将其合并并加入状态中。由于 $50$ 以内大约只有 $15$ 个质数，所以时间复杂度可以通过。
受小数据启发，我们依旧考虑状态压缩，但是同时也加上根号分治的优化。对于一个物品 $i$：
$(1) ~ i \leq \sqrt{n}
此时可以直接使用状态压缩，时间复杂度可以接受。
(2) ~ i > \sqrt {n}
此时我们用大于 \sqrt{n} 的质因数对剩下的数按照每个大质因数的倍数进行分组。由于两个大于 \sqrt{n} 的质数的 \operatorname{lcm} 大于 n，所以组与组之间的选取情况互不干涉。而在组内，我们又只能选取最多 1 个数，所以我们只需记录这些数的乘积包含的小于 \sqrt{n} 的质因数的情况即可进行快速转移。这样的复杂度稍加分析之后发现同样可以接受。
综上，我们可以以较快的速度通过这道题。
由此，我们可以得到一些启示：在时间复杂度爆表时，灵活地使用根号分治可以大大的优化时间复杂度。
总结一下
普通的背包固然简单，但是在其基础上稍加变形就可以使题目难度陡然增加。背包题目也灵活多样，可以和贪心、搜索、根号分治结合，在今后的做题时一定要多往这方面想想。
区间 DP 总结
与一些典型 DP 不同，区间 DP 的时间复杂度一般都为 O(n^2) 起步，O(n^3) 常见，甚至可能是 O(n^4)、O(n^5) 的，所以数据范围很容易暴露做法。而区间 DP 最棘手的问题主要是：如何设计合法的状态使得能够正确转移、如何不重不漏的转移。
由于区间 DP 没有固定的模板，所以直接以例题来进行经验总结。
表达式的亿种可能性
求啥设啥。设状态 f_{i,j} 表示 [i,j] 内所有可能的结果的总和。
对于一个区间，我们肯定要枚举一个最后使用的运算符。设枚举的断点为 k。
对于三种不同的运算符，有两种不同的情况。
(1) ~ op_k = +
直接将 f_{i,k} 和 f_{k+1,j} 加起来肯定是不行的，因为这完全没有体现将两个小区间内的所有情况合并起来的过程。考虑推式子分析。
设左半区间可能的计算结果数为 k_1，每种计算结果为 c1_i；右半区间可能的计算结果数为 k_2，每种结算结果为 c2_i。可得：
\begin{aligned}
f_{i,j} &= \sum\limits_{i=1}^{k1} \sum\limits_{j=1}^{k2} c1_i + c2_j
\\
&= \sum\limits_{i=1}^{k1} (c1_i \times k2 + \sum\limits_{j=1}^{k2} c2_j)
\\
&= \sum\limits_{i=1}^{k1} c1_i \times k2 + f_{k+1,j}
\\
&= k1 \times f_{k+1,j} + k2 \sum\limits_{i=1}^{k1} c1_i
\\
&= k2 \times f_{i,k} + k1 \times f{k+1,j}
\end{aligned}
而由于 k1 = (k-i)!，k2 = (j-k-1)!，所以转移为：
f_{i,j} = f_{i,j} + (j-k-1)! \times f_{i,k} + (k-i)! \times f_{k+1,j}
(2) ~ op_k = -
类比加法即可。
(3) ~ op_k = \ast
由于乘法具有分配率，可以直接得到：
f_{i,j} = f_{i,j} + f_{i,k} \times f_{k+1,j}
最后还有一个问题：虽然两端区间内部的顺序已经可以认为被固定，但是两端区间的相对顺序还没有固定，导致转移统计漏。这时，我们便需要考虑乘上一个系数。可以这么求：区间内的所有符号先任意排列，而由于两段内部顺序已经固定，所以要将两段内部的排列种数除掉。即为：
\frac{(j-i-1)!}{(k-i)!(j-k-1)!} = \tbinom{j-i-1}{k-i}
祖玛游戏
这个题主要难在状态设计。由于只开两维状态无法得到一些关键信息，例如端点旁连续且相同的字符数量。既然不好得到信息，就将其加入状态中。
设 f_{i,j,k} 表示删除区间 [i,j]，其中 i 左边有 k 个与 i 连续且相同的弹珠，所需的最小代价。由于 k 只需要大于等于 m 即可消除，所以第三维的 k = \Theta(m)。
这里有一个很重要的性质：要让代价最小，肯定要让两个本不相邻且颜色相同的珠子在删除后相邻。
那么就可以推转移了。首先考虑加珠子，有两种情况：
(1) ~ k = m-1
此时算上 i 之后就有 m 个和弹珠 i 颜色相同的弹珠，所以左边可以删除。此时：
f_{i,j,k} = f_{i+1,j,0}
(2) ~ k \neq m-1
此时可以考虑在做段添加一枚弹珠，代价 +1，即：
f_{i,j,k} = f_{i,j,k+1} +1
再考虑删除。由最优性质可知，我们要找一个断点 l，使得珠子 i 和珠子 l+1 颜色相同，这样可以保证在删除 [i+1,l] 之后 i 和 l+1 可以在一起。转移为：
f_{i,j,k} = f_{i+1,l,0} + f_{l+1,j,\min \{ k+1,m-1 \}}
这里由于连续弹珠数量只要 m 个就能删除，所以第三维只需要和 m-1 取最小值即可。最后答案即为 f_{1,n,0}。注意，k 要倒序枚举。
[CSP-S 2021] 括号序列
设 f_{i,j} 表示区间 [i,j] 的合法括号序列的数量。按照情况分别讨论即可。
但是在以下情况中会算重：
(\cdots)\ast \ast \cdots \ast (\cdots) \cdots (\cdots)
这本质上只是一种情况，但是由于枚举的断点不同，就会把这种方案多次计入答案。所以，我们需要钦定一种唯一的转移，使得只被转移一次。
先预处理出 vis_{i,j} 表示区间 [i,j] 是否是 S。
设 f_{i,j,0} 表示情况：(\cdots)，即 (A) 或 (S)；
$f_{i,j,2}$ 表示情况：$\ast\ast()**\ast()\ast\ast\ast()$，即 $SA$；
$f_{i,j,3}$ 表示情况：$()\ast\ast\ast()\ast\ast()\ast\ast\ast$，即 $AS$。
那么转移就比较好推：
$(1) ~ f_{i,j,0}
由定义可知两端必须是匹配的括号。由题可知 (S),(A),(AS),(SA) 均合法，所以：
f_{i,j,0} = f_{i+1,j-1,1} + f_{i+1,j-1,2} + f_{i+1,j-1,3} + vis_{i+1,j-1} ~ [a_i='(' ~ or ~ a_i='?',a_j = ')' ~ or ~ a_j = '?']
这里不加上 f_{i+1,j-1,0} 的原因是：f_{i,j,2} 包含 f_{i,j,0} 的所有方案。
(2) ~ f_{i,j,1}
肯定要枚举断点。这里只考虑一种转移：右边是一个情况 0。
在这种情况下，左边要么是情况 0，要么是情况 1，要么是情况 3，而情况 0 \in 情况 1，所以只用算情况 1 和情况 3。
方程为：
f_{i,j,1} = (f_{i,k,1} + f_{i,k,3}) \times f_{k+1,j,0}
而这只考虑了两段合法括号序列拼接的情况，并未考虑 (\cdots) 的情况，所以还要加上 f_{i,j,0}。
(3) ~ f_{i,j,2}
显然，直接拆成 S 和 A 即可：
f_{i,j,2} = vis_{i,k} \times f_{k+1,j,1}
(4) ~ f_{i,j,3}
直接拆成 A 和 S：
f_{i,j,3} = f_{i,k,1} \times vis_{k+1,j}
最终答案为 f_{1,n,1}。这样的转移有效地避免了重复。
[JXOI2018]守卫
由于 n \leq 5 \times 10^3，所以只有 O(n^2) 的时间复杂度才能通过。
我们可以利用那些斜率开始变大的点，将区间划分成很多个山谷。有一个很重要的性质：两个不同山谷之间的点互相看不见。所以最后一个能被右端点看到的点的左边第一个点只能自己放或被它右边的点看。设最后一个能被右端点看到的点的下标为 p，则转移为：
f_{i,j} = \min \{ f_{i,p-1} , f_{i,p} \} + f_{p,j}
而 p 可以很简单的求出：先枚举右端点 j，再从大到小枚举 i，只要一个 i 满足他与 j 的连线的斜率比原先的最小斜率还小，他就是新的 p。这样做的时间复杂度就能通过了。
这告诉我们：改变枚举顺序有时可以帮助我们更好地维护一些信息。
解题任务
一个人 i 能做题目 j，当且仅当：
l \leq a_i \leq j \leq b_i \leq r , k \leq c_i
其中 k 是题目的难度。但是如果单纯去枚举每个人的话，每次的时间复杂度为 O(m)，无法接受。
如果我们建立一个空间，把三个点的范围放到空间中，就会得到一个长方体。这可以使用三维前缀和在 O(1) 时间内求得。
由于一个人做的题是当前区间难度最小的题，所以我们要将其加到状态里。
设 f_{i,j,k} 表示考虑题目区间 [i,j]，其中难度最小值为 k，能得到的最大权值。枚举这个区间内第一个被做的题，则剩下所有题的难度都必须不小于当前题的难度。设第一个被做的题编号为 p，状态转移即为：
f_{i,j,k} = \max_{k1 \geq k,k2 \geq k} \{ f_{i,j,k} , f_{i,p-1,k1} + f_{p+1,j,k2} + w(i,j,k,p) \times k \}
其中 w(i,j,k,p) 表示能做的题目区间为 [i,j]，能做题目 k，且权值 c 不小于 p 的人数。
这样直接枚举，时间复杂度为 O(n^3m^3)。由于 k1,k2 是一段后缀，所以可以考虑使用后缀最大值优化，时间复杂度为 O(n^3m)。
总结一下
区间 DP 的范围一般会暴露做法。不过，区间 DP 很难找到固态模板，其题目可以出得非常灵活。自我感觉，区间 DP 最难的地方是在如何在能够通过的时间内得到全部的、正确的解，而这需要通过大量练习来培养感觉。