wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

动态规划

背包模型

[[ item.c ]]

dp处理技巧

## 完全背包模型
一般应用的场景有，切成若干个段，放进若干个物品

* 一次可以同时选若干个$$x$$，即选$$k \cdot x$$

* 划分成若干段，每一段的长度是$$k \cdot x$$

对于第一种情况，一次选若干个$$kx$$，怎么处理呢？
**从 0 开始，每次只加入一个$$x$$**，这样将一次同时选若干个，拆成**一个阶段，选若干次，每次只能加入一个$$x$$**
即$$dp(i, V) \to dp(i, V+x)$$，从小到大选，选了$$x$$之后，**阶段不变**
这样就有转移方程
```math
\displaystyle
dp(i, V) \leftarrow dp(i-1, V) \\
dp(i, V) \leftarrow dp(i, V-x) + cost(x)
```
### Codeforces Round 1046 (Div. 2)
**[C. Against the Difference](https://codeforces.com/contest/2136/problem/C)**
给定块状数组，全部都由一个数组成，这个数等于数组的长度
比如`[1], [3, 3, 3], [2, 2]`是块数组，但是`[1, 2], [2, 2, 2]`不是
再给定一个序列`a`，它是好的，当且仅当它存在子序列，这个子序列可以由若干块状数组拼接而成，不要求连续
求最长子序列长度

**算法分析**
很明显的`dp`，但考虑到转移，$$i$$这个位置选还是不选，如果选的话$$x = a_i$$，可能的转移如下
考虑从哪里切下来，可能最后一段的长度是$$kx$$，$$dp(i) \leftarrow dp(i - kx) + kx$$
但是直接做，$$x$$是确定的，你还需要枚举$$k$$，复杂度就炸掉了

那么这种式子怎么优化呢？这就是**类似完全背包的优化**，从小到大枚举$$i$$，一次只考虑加入**一个$$x$$**
这样从`x`第一次出现，到之后出现若干次，它对 dp 值有贡献
当且仅当$$0 \to x \to 2x \to 3x \cdots \to kx$$，**最后一段，仅考虑加入一个长是$$x$$的段**
这样转移方程是$$dp(i) \leftarrow dp(i-x) + x$$

在这个问题中，我们预处理$$x$$出现的所有位置`pos`，考虑$$i$$位置的时候，找到它在`pos`中的下标
假设说是$$p$$，那么`j = pos[p-k+1]`，就有转移$$dp(i) \leftarrow dp(j-1) + x$$

## 前缀最大最小
### Accepted极限代码巅峰赛
还有一类 dp 问题，可以转化成前缀最大/最小来解决
**[Easy Partition](https://ac.nowcoder.com/acm/contest/91849/B)**
给定一个序列$$n$$和一个$$K$$，要将序列划分成若干个非空的段，假设第`i`个非空段是$$[l_i, r_i]$$
现在要求
```math
\displaystyle
\sum_{k \mid i} \sum_{j \in [l_i, r_i]} a_j
```
即所有编号是$$k$$的倍数（段编号从 1 开始）中的所有数的和，求最大的可能权值

**算法分析**
注意到，如果上一个**有效的**段的最后一个元素下标是$$j$$，那么要求$$[j+1, i-1]$$之间至少有$$k-1$$个数
那么$$i$$才能作为新的有效段，也就是说，$$j \leqslant i - K$$

如果$$i$$作为新的有效段，存在转移
```math
\displaystyle
\begin{cases}
dp(i) \leftarrow \max_j \{dp(j)\} + a_i \\
j \leqslant i - K
\end{cases}
```
而`j`如果越往左边，`[j+1, i-1]`的间隔只要$$> K-1$$，我们总可以通过合并某些段，让其间隔恰好为$$K-1$$
也就是说，上述转移对于$$j \leqslant i - K$$总是成立的，当然$$i \geqslant K$$
（此时中间的段没有用了，怎么合并都无所谓）

上述式子，可以用一个$$pre(i)$$维护前缀`dp`最大值，$$pre(i) = \max(dp[1\cdots i])$$

还有一个转移，就是$$i$$这个位置不开新的段，和前面的合并，那么只要$$i \geqslant K$$
自然有$$dp(i) \leftarrow dp(i-1) + a_i$$
```bash
chmax(dp[i], dp[i-1] + a[i]);
chmax(dp[i], pre[i-K] + a[i]);

chmax(pre[i], max(pre[i-1], dp[i]));
```

## 每次只加入最低的 1
### 2025“钉耙编程”算法设计暑期联赛6
**[cats 的 max](https://acm.hdu.edu.cn/contest/problem?cid=1177&pid=1008)**
给定$$n \times m$$的矩阵$$a(i, j)$$，选出若干行，使得选出的编号是$$p_1, p_2, \cdots, p_n$$
定义方案的权值是
```math
\displaystyle
\sum_{i = 1}^{m} \max \{ a_{p1, i}, a_{p2, i}, \cdots, a_{pk, i} \}
```
求所选方案的最大值，$$m \leqslant 13$$

**算法分析**
如果$$K \geqslant m$$，那么很显然，所有$$m$$列的最大值都可以选的到，直接暴力
否则的话，只能选一部分

考虑状态压缩，$$(i, mask)$$表示$$i$$这一行，对最终最大值有效贡献的位是`mask`
那么最终所有`mask or`起来，应该是`(1<<m) - 1`，考虑子集`dp`
不难写出来这样的转移
```bash
for i = 1 to K 表示阶段
	for mask = 枚举 i 阶段的 mask，i 阶段新添加了哪些位？这些位肯定都是某一行提供的
		for sub = subset of mask, 枚举子集，表示 i 阶段新添加了 sub 表示的位
			chmax( dp(i, mask),  dp(i-1, mask^sub) + cost(sub) )
```
那么难点就是`cost(sub)`怎么算，注意到，`cost(sub)`肯定由某一行提供的，可以预处理，形如
```bash
for i = 1 to n 枚举每一行
	for sub = 1 to (1<<m)-1 枚举所有状态
		chmax( cost[sub],  cost[sub0] + (a[i] 中所有 sub 为 1 的 j，+a[i, j] ) )
```
现在的问题就是，我们可以考虑$$cost(sub0) \to cost(sub)$$的转移
其中$$sub0$$由$$sub$$中**抠掉一个`sub`中本来为`1`的位转移过来**
抠哪一个呢？这里同样用到了一个技巧
```bash
for sub = 1 to (1<<m)-1，从小到大
	auto sub0 = sub xor (1<<lobit(sub))，即每次只加入最低为 1 的那个位，j = lobit(sub)
	chmax(cost[sub], cost[sub0] + a[i, j])
```

> 这也是分多次加入，每次只加入最小单位
否则的话，正常做要枚举`for sub0 in subset(sub)`，然后`d = sum(sub xor sub0)`
做转移$$dp(sub) \leftarrow dp(sub0) + sum(sub \oplus sub0)$$，这样时间复杂度承受不了
遇到这样的递推转移，可以从小到大枚举`sub`，每次只加入**最低位的那个`1`**

这样处理完每一行之后，就可以得到一个`cost[ mask = 可能的所有状态 ]`表
我们用`chmax( COST[mask], cost[mask] )`来更新**全局的 COST[mask]**
表示当我们要弄出`mask`时，应该选哪一行，它的最大价值是多少，这样就做完了

看完文章有啥想法

算法小站

wiki 主题

动态规划

dp处理技巧

目录