0%

挑战程序设计竞赛 02 章 01

第二章是算法入门,讲了搜索、贪心、DP等等基本算法里的基础部分简单的数据结构,是为初级篇。

这篇讲搜索、贪心和DP的部分。

多校赛好难。

穷竭搜索

最暴力的算法,完全依靠计算机的算力解题。对于有先后状态的可能解集合,有先根据某个状态的一种可能转移搜索下去的深度优先搜索,和先搜索某个状态的所有可能转移的宽度优先搜索。

递归

递归指在一个函数再次调用该函数。

对于拥有子状态的问题,利用递归的算法可以牺牲时间和空间,换来思路比较清晰的代码。

例如求斐波那契数列可以采用递归,注意递归函数一定要有停止条件

1
2
3
4
long long fib(long long n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}

由于上述代码运行时有参数相同的 fib(n) 被调用了许多次,可以将它先记录下来。这是后面会见到的DP思路。

一个先进后出的数据结构,通过 push 将一个元素进栈,pop 将栈顶的元素取出。C++标准库 <stack> 的栈需要用 stack::top 来获得栈顶的元素,stack::pop 只是移出元素。

栈的性质被用来保存调用函数时的“现场”。调用者的相关数据和参数被push到栈中,被调用的函数处理结束后,记录返回的地址,把栈顶不再使用的数据清除,即可回到调用函数的位置,继续执行之后的语句。

显然规模较大的递归会让调用栈增长到相当高的地步,调用函数的开销不仅占用时间,还会花费很大的栈空间。实际上前例求斐波那契数列的递归算法在 n = 40 时就已经需要很长的时间来完成执行。它的时间复杂度是 $O(2^n)$。

队列

一个先进先出的数据结构。C++标准库的队列在 <queue> 中定义,其中 queue::pushqueue::popqueue::front,分别用来存入、移出、获得元素。

深度优先搜索 DFS

深搜从当前状态的一个可能状态开始不断转移,直到无法转移为止,再从下一个可能状态开始重复。显然这样不断嵌套下去的搜索方法适合用递归实现。

递归可以用来解决规模较小的背包问题

突然感觉OI Wiki上的好像更全啊。啃完这本考虑去通读一下。(能吗

部分和问题

给定 $n$ 个正整数,判断是否能从中选出若干个数,使它们的和恰为 $k$。

显然暴力一点的做法是从第一个数开始,每个数选择取或不取,一直到最后一个数,此时和为 $k$ 则可以。所有可能都搜完之后还没有遇见可行解,则不行。最差情况是一直搜到最后一种组合都没有可行解,复杂度 $O(2^n)$。在 $n$ 较小的情况下用DFS可解。

大概代码

1
2
3
4
5
6
bool dfs(当前位置, 和) {
if (到最后一个数)return 和 == k;
return dfs(下个位置, 和); // 不选当前数
return dfs(下个位置, 和 + 当前数); // 选当前数
return false;
}

Lake Counting (POJ 2386)

大小为 $N \times M$ 一个园子积了水。八连通 (有公共顶点) 的积水块被视作连在一起,求园子里共有多少片互相不连通的水洼。

从一个有积水且没被搜过的块开始,深搜连接的块,把搜索到的地方记录一下供后续检查。搜完一次即多一片连接的水洼,直到所有积水处都被搜索过。最差情况每个格子被搜索一次,复杂度 $O(8 \times N \times M) = O(N \times M)$。

考虑到输入的积水情况不需要保留,为了简化判断流程,省去记录表的空间,可以每搜到一块积水就把它换成旱地,直到整片园子没有积水。

宽度优先搜索 BFS

宽搜优先处理当前状态所有可能的“下一步”,“均匀地扩散”到覆盖所有状态。它不需要一次走到头,所以不使用递归来实现。宽搜使用队列来存储将要搜索的状态。

搜索时,宽搜将初始状态入队,此后则不断从队首取出状态,同时将该状态可以转移到的未搜索状态入队,直到找到解或队列为空。由队列的性质可知状态是按照距初始状态由近到远的顺序被搜索的。

迷宫最短路

给定一个矩形迷宫。迷宫由通道和墙壁组成,从一个通道可以走到与它四连通的通道。求出从起点到终点需要走的最短步数。输入保证从起点可以走到终点。

由宽搜的搜索顺序可以发现,如果搜索到了终点,则搜索路径一定是最短的。此处一个状态可以由坐标来描述。

用一张表来标记搜索到的状态。将01标记换成路径长度,这张表同时可以用来记录从起点到该格的最短步数,此时“未搜索”需要用充分大的常数来标记。注意溢出。

大概代码

1
2
3
4
5
6
7
8
9
10
11
12
int bfs() {
queue<point> q;
初始化表;
起点入队;
记录起点;
while (!q.empty()) {
取出前端状态;
if (该状态是终点) break;
将该状态可转移到的未搜索状态入队, 同时记录到这些状态的距离;
}
return 到终点的距离;
}

如果要记录到终点的路径,只需要在搜索到的状态里标记好它的上一个状态,搜索结束后就可以从终点倒序回到起点。部分情况下最短的路径取决于宽搜时状态入队的顺序。

DFS 和 BFS

深搜和宽搜都可以遍历所有的状态,从能解决问题的角度来看,是可以互相替换的。但是两者各有更高效的利用方向。

对于需要搜索所有状态的问题,深搜需要的空间比宽搜要小。宽搜需要一个队列来存放所有的状态,而深搜只需要系统提供的栈。

对于搜索最短路径的问题,宽搜更有优势。宽搜搜到的第一个解必定是转移次数最少的解,而深搜搜到的第一个解取决于每次转移时的方向。只有对所有的可行解继续遍历一遍,深搜才能给出最近的解。但是也有使用宽搜的转移顺序,同时尽量节约空间的“迭代加深深度优先搜索(ID-DFS)”,在此书的4.5节。

枚举特殊状态

C++ 标准库中提供了一些用来代替简单深搜的函数,比如用next_permutation来对所有元素进行全排列。

一些其他的可行解空间生成可以使用特殊写法,比如用位运算生成 $C_m^k$ 的所有排列,在此书的3.2节。

剪枝

我们有的时候不需要知道所有可行解而只想知道“可不可行”,也有的时候发现穷竭搜索在一个已经不可解的状态下面到处乱搜。对于第一种情况,在搜到第一个解时结束搜索即可省去时间。而第二种情况需要更加精细的剪枝策略。

例如深搜解决部分和问题时,如果各元素都非负,那么一旦和超过了 $k$,后续所有的选择就都不可能把和拉下来,直接结束这部分的搜索就可以省去不必要的时间。

更加难懂的搜索手段在此书4,5节。

栈内存和堆内存
为了保存调用现场,主调函数的所有局部变量都要储存起来,这个储存位置叫做栈内存。而使用 newmalloc 获得的内存在堆内存里。
栈内存一经分配则无法扩大,也即函数递归的层数是有极限的。Windows下一般的大小为1MB,通常允许上万次递归。Java可以在执行程序时指定栈大小,C++可以在编译时添加 -Wl,--stack=536870912 分配栈区大小为512MB。
出于减少命名重复和提高耦合度等原因,不推荐使用全局变量,但是对算法竞赛这样规模的代码,大可以为了方便而破戒,也不会带来太麻烦的调试成本。
为了给递归留出空间,巨大的变量可以放在堆上。大变量通常会定义得比数据规模上界再多一点点,给字符串后缀0和1-n下标留点余地。


贪心

可以用贪心解决的问题一般有这样的特点:遵循某个规则,选择每个部分状态最优的转移方向,最终能到达整体的最优解。

硬币问题

有1元、5元、10元、50元、100元、500元面额的硬币若干枚,用来支付 $A$ 元,求最少需要的硬币枚数。输入保证有解。

傻子(无意冒犯,我以前也是现在还是)才会搜索出所有可行解然后取最小值。显然优先选择大额硬币就能获得总数最少的解。

上例即最简单的贪心解法。它有目的地选择某个转移方向并且相信最终的状态一定是最优解。而之前的深搜和宽搜选择转移方向的策略,只是以“最终能遍历所有方向”为目标。

此题也可以看作一个背包问题。选择一定数量的硬币使最大面额等于 $A$,或者选择 $A$ 面额的硬币使数量最小。背包问题通常的动态规划解法也是遍历了多个可行解,效率上不如贪心。

区间调度问题

有 $n$ 项任务,每项任务在 $s_i$ 时刻开始,在 $t_i$ 时刻结束,对每项工作都可以选择参与与否,但不可中途停止。参与的时间不能重叠,上一项任务开始和和下一项任务结束的时刻相同也是不允许的。给出各任务开始和结束的时刻,求一种选择策略使能参与的工作最多。

贪心的策略有时是比较难找的。这题有几个典型的贪心策略:

  1. 在可选任务里选择开始时间最早的
  2. 在可选任务里选择结束时间最早的
  3. 在可选任务里选择用时最短的
  4. 在可选任务里选择与其他任务重叠最少的

仔细思考一下各个策略有没有反例:

  1. 一个长任务从头到尾覆盖了多个可以连续执行的短任务
  2. 这是对的
  3. 一个短任务和两个更长的任务重叠
  4. 通过多次重复相同起止时间的任务掩盖最优解

代码实现上,对所有任务按结束时间排一个升序,记一下当前最后一个结束时间,然后挨个选就可以了。

贪心方法的证明
选取了相同数量的任务时,按贪心算法选取的任务结束时间不会更晚。
若存在更优的方案,则在选择结束后,更优的方案选择的任务比贪心多。设贪心选了 $n$ 个,更优选了 $n + k$ 个,则在都选了 $n$ 个时,贪心结束时间不晚于更优,那么更优的后 $k$ 个任务也可以被贪心选择,贪心并未结束选择。
则可反证不存在更优的方案。

一般做题时,尤其是打比赛做题时,不需要详细的证明来背书,只要能 A 就行了。但拿不准或者 WA 了的时候还是仔细考虑一下吧,虽然不觉得这个情况下能证出来什么东西。

Best Cow Line (POJ 3617)

给定一个字符串 $S$,从空字符串开始构造一个等长的字符串 $T$,以下列任意操作构造:

  1. 从 $S$ 的头部删去一个字符,添加到 $T$ 的尾部
  2. 从 $S$ 的尾部删去一个字符,添加到 $T$ 的尾部

求字典序最小的 $T$。

首先想到的是比较当前 $S$ 的头尾,把字典序更小的字符加到 $T$ 的尾部。如果遇到相同的字符如何处理?

遇到首尾是相同字符时,为了使较小的字符更早地加入到 $T$ 中,需要比较第二个和倒数第二个字符的大小,直到遇到不同的字符,把较小字符那一侧的首/尾字符加入 $T$。

具体实现,可以用一个字符串和双指针(四指针?),也可以用原字符串和一个翻转的字符串,这样更方便表示。中止条件可以是两个指针相遇,也可以是 $T$ 的长度和 $S$ 相等。

一般情况下,求字典序最小的问题可以使用贪心,也可以在搜索时向最小字符转移。

(这题会卡输出,一行 80 个字符。)

Saruman’s Army (POJ 3069)

直线上有若干点,从中选出一部分点打上标记。对每个点,以它为圆心的一个半径内(包括自己)必须有至少一个被标记的点。给定点的总数和半径,求被标记的点数量的最小值。

这个题面是很精简的模型题,可以用到比如说(直的)城墙上设置望楼,(直的)防线上设置哨塔,(一维的)草坪上设置灌溉器。

这样的最大覆盖题显然要充分利用各个已经标记的点。首先第一个点不用标记,向后走一个半径,遇到的最后一个点打上标记,再从它开始走一个半径,遇到的下一个点,处理方式和第一个点相同,如此一直到走完所有的点。

需要两个循环来让指针向后走。要注意的是循环停止的条件,首先是下标不越界,然后为了直观,走到的距离不大于上一个记录的距离加上半径,之后是指针加减 1 的操作。两个记录,一个是“开始的点”,另一个是打上标记的点。这样一个“圆”覆盖的范围只需要标记一个点。注意边界的处理。

Fence Repair (POJ 3253)

为了准备维修栅栏的材料,需要切割一块很长的木板。不考虑切割损耗,木板的长度正好是所有木料的长度和。切断一块木板的代价为该木板的长度。求最小的总代价。例如将长度 $21$ 的木板切割成 $5、8、8$ 三段的最小代价为 $21 + 13 = 34$。

代价和长度有关,那么一段木料被切出来得越迟,它对代价的贡献就越久。显然我们希望这样的木料越短越好。那么从最后一次切割回溯,每次最短的和次短的拼在一起计入代价,就可以得到最小的代价。这也是一种贪心。

大概实现,每次找出最短和次短,将它们拼合,计入代价,然后将拼回去的木板放到原来的数组里直到剩余木板为 1。这里之前的两个位置已经用过了,可以被新木板覆盖,或者记录一下跳过。更好的做法是拼好之后和数组最后一个元素交换一下,这样遍历的开销会递减,剩余木板的数量也可以当作遍历的停止条件。

霍夫曼编码 (Huffman Code)
由于一条信息中各字符出现的次数不尽相同,用同一长度的编码去表示每个字符,出现次数较少的那些字符难免会引起浪费。霍夫曼编码提供了这样一种编码方式:对于出现多次的字符,用较短的编码表示,而出现次数少的字符可以用长一点的编码。只要解决不同长度编码间的识别问题,这样的编码方式就可以极大地节省空间。事实上,霍夫曼编码是码字长度为整数时最优的编码方案。
显然霍夫曼编码是由各字符频率确定的。利用二叉树构造霍夫曼编码时,将频率最低的两个字符作为子结点合并,它们的频率和为父结点的频率。以父结点为代表,继续参与构造,直到所有的结点都被包含在一棵二叉树里。编码时,从根开始,向右为 0,向左为 1,直到遇到一个字符,所经过的 01 序列就是该字符的霍夫曼编码。这些 01序列可以不加分隔地连在一起,表示整条信息。只要序列没有缺损,就不会出现错误识别的情况。
(这个怎么证明?)


动态规划 (DP)

动态规划,Dynamic Programming,DP,是常考的题型。当一个问题的子状态有马尔可夫性时,它可以使用 DP 求解。马尔可夫性指子状态的后续转移概率与且仅与该子状态有关,而与之前的状态和到达该子状态的路径无关。大概是这样。又称无后效性,即一个子状态有最优解后,之后的各种决策不会影响它最优解的效果。通俗一点说,就是可以拿到一个递推公式。当然如果能算出通项的话还是直接代更快。

记忆化搜索与 DP

所谓记忆化搜索,就是记住之前搜索过的状态,在下一次遇到时直接查询搜索历史,减少重复搜索的开销。

01背包

有若干个给定价值和重量的物品,从中选择总重量不超过 $W$ 的物品,使价值和最大。

首先能想到暴搜,对每个物品都向选和不选两个方向转移。大概代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 从search(0, 空包容量)开始
int search(当前物品序号, 当前剩余容量) {
int res;
if (没有物品了) {
res = 0;
} else if (当前物品放不进去) {
res = dfs(下一个物品序号, 当前剩余容量);
} else {
// 在取和不去当前物品中选最优
res = max(dfs(下一个物品序号, 当前剩余容量), dfs(下一个物品序号, 当前剩余容量 - 当前物品重量) + 当前物品价值);
}
return res;
}

前面已经讲过这类的搜索是 $O(2^n)$ 的,一旦物品稍微多一点就会炸。

为了优化这个算法,先把它的递归树画出来看一下。如果样例不是那么巧,很容易发现部分中间结点拿到了一样的参数,而且之后长出来的子树也是完全一样的。实际含义就是无论之前是怎么取的,当取到同一个物品,且剩余同样的空间时,后续的最优解都是一样的。很容易回推得到出现这样局面的原因是之前有若干个物品,其中一个物品的重量等于其它物品的和。那么把这样的状态记录一下,下次遇到时直接查询结果,就可以大大节约时间。此处只需要一张 $n \times W$ 的表就可以存下所有搜索结果(可能是相当稀疏的),复杂度为 $O(nW)$。注意初始化。

这就是记忆化搜索。

然而,如果不小心写成了这样:

1
2
3
4
5
6
7
8
9
10
11
12
int search(当前序号, 当前容量, 当前总价) {
int res;
if (没有物品了) {
res = 当前总价;
} else if (当前物品放不进去) {
res = dfs(下个序号, 当前容量, 当前总价);
} else {
// 在取和不去当前物品中选最优
res = max(dfs(下个序号, 当前容量, 当前总价), dfs(下个序号, 当前容量 - 当前重量, 当前总价 + 当前价值));
}
return res;
}

这样多拿参数比较方便剪枝,但是这样拿到同样参数的结点就没了。

上一段代码的每个调用状态都是和之前的状态通过 当前总价 增强了联系。它和上上段代码是什么关系呢?第一段代码尽量剥离了子状态和之前状态之间的关系,只要两个参数一样,后续的解法就是一样的。而第二段代码多了一个参数,这参数暗示了之前可能选择的物品,这样一来就从另一个角度描述了这个状态:具体的选择方案。实际上这题不需要给出方案,也就没必要浪费空间记录到每个状态的路径。两段代码结构很像,但是第一段的 res 记录后续能选择的最大价值,而第二段的记录一直以来能拿到的最大价值,可以写成全局变量。含义几乎是相反的。

接下来我们看一下记录搜索用到的这个表。

记这张表为 $dp[i][j]:=从第 i 个开始挑选总重小于 j 的物品时,可以获得的最大价值$。于是有如下递推关系:

  • 从第 $n$ 个(下标为 $0$ 到 $n - 1$)开始挑选时,总为 $0$。
  • 从第 $i$ 个物品开始挑选
    • 如果当前物品超重,则当前可挑选最大价值,和从下一个物品开始挑选是一样的。
    • 如果当前物品可选,则当前可挑选的最大价值,是不挑选当前物品,和挑选当前物品两个方向中的最大值。

换到公式来说就是:

那么只要把这张表算出来就行了,用不用递归的搜索其实无所谓。随着递推,第一个坐标减小,第二个增大或不变。大概代码:

1
2
3
4
5
6
7
8
9
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j <= W; ++j) {
if (j < w[i]) {
dp[i][j] = dp[i + 1][j];
} else {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
}
}
}

最后的答案存在从第一个开始挑选重量 $W$ 的位置,就是 dp[0][W]。这显然比递归更加简洁。

改变 DP 数组的定义就可以改变填充 DP 数组的方向。定义 $dp[i + 1][j]:=前i个物品中选择总重j以内的最大总价$ 就可以从左上向右下填充数组。

以上是从递推的角度讨论 DP。如果是从状态转移的角度看,一个当前状态可以通过取和不取向两个状态转移,即“前 $i$ 个中取重量 $j$ 以内”向“前 $i + 1$ 个中取重量 $j + w[i]$ 以内”(取)和“前 $i + 1$ 个中取重量 $j$ 以内”(不取)两个状态转移。其中取的转移需要看能不能装得下。转移过去后是否覆盖目标状态,则是看哪个更大。

为了节省内存,可以尝试压缩空间。注意到每次转移只涉及数组的两行,可以把整个 DP 数组简化到只有两行,通过一个跳转来实现“滚动”填充。这需要 $i$ 的状态完全转移到 $i + 1$。

也可以压成一行。观察填充 $dp[i + 1][j]:=从前i个物品中取不超过j重量的最大总价$ 的代码:

1
2
3
4
5
6
7
8
9
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= W; ++j) {
if (j < w[i]) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}

在装不下当前物品时,没有发生更新而是直接继承上一个状态,能装下当前物品时,则更新到最优解。此时可以发现:滚动数组中“上一行”的某个数据如果仍然是最优解,它的数据是可以被保留到“这一行”的,否则在“这一行”中会被新的最优解替换。那么就可以再砍掉一行:

1
2
3
4
5
for (int i = 0; i < n; ++i) {
for (int j = w; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}

注意循环方向变了,因为01背包每次转移依赖“上一行”的前项。

01背包 · 大

如果你的背包变得特别大,之前 $O(nW)$ 的复杂度就会出问题。不妨换个思路。以前是同重量取最大价值,现在是同价值取最小重量,那么复杂度会变成 $O(n\sum_i v_i)$。

则定义 $dp[i+1][j]:=前i个物品中挑选价值为j的最小重量$,这样填充结束后,答案就是使 $dp[n][j]\leq W$ 的最大的 $j$。

则前 $i$ 个物品中选总价为 $j$ 的状态由来自两个方向的转移得到:

  • 前 $i-1$ 个物品中选总价为 $j$ 的重量
  • 前 $i-1$ 个物品中选总价为 $j-v[i]$,加上第 $i$ 个的重量

注意初始化时还要引入充分大。

两个方向取最小值覆盖。

当背包容量和全部价值和都相当大的时候就没了。

最长公共子序列 LCS

给定两个字符串,长度分别是 $n$、$m$,求它们最长公共子序列的长度。

Longest Common Subsequence 是经典的字符串问题。

用 DP 解决时可以定义 $dp[i+1][j+1]:=串S的前i子串和串T的前j子串对应的LCS长度$。则两个子串各增一个字符时,新的字符串的 LCS 可能是:

  • 旧 LCS 加上新字符
  • $S$ 的旧子串和 $T$ 的新子串的 LCS
  • $T$ 的旧子串和 $S$ 的新子串的 LCS

两个旧子串的长度可以不相等,由此能填充整个数组,复杂度 $O(mn)$。

另一种推公式的方法是从后往前推,先判两个完整字符串,再不断地去掉后缀。

从表的右下角向左上角回溯,每一个使转移方向斜着(加一)的项就是 LCS 里的一项,所以记录一下转移方向就能得到子序列本列。

这个东西可以用来查重。

递推与 DP

DP 基本就是递推。

完全背包 01

$n$ 种给定重量和价值的物品,从中选择总重不超过 $W$ 的物品,使选出的物品总价值最大。每种物品可选任意多件。

首先确定 DP 数组的定义:

则有递推关系:

  • 前零种和总重零显然是 $0$
  • 设第 $i$ 种选了 $k$ 个
    • 第 $i$ 种不可选时,$k=0$
    • 第 $i$ 种可选时,从前 $i - 1$ 种扣除 $k \times w[i]$ 的重量,用于选择第 $i$ 种

则前 $i$ 种的最优方案是 $k$ 从 $0$ 一直到装不下为止,所有状态中的最大总价。那么可以写出一个三重循环。

这个算法的最坏情况是,遇到重量为 $1$ 的物品时,$k$ 从 $0$ 一直增长到最多 $W$,加上外面两层循环,复杂度 $O(nW^2)$,不算好。

用解决第一个背包问题的思路,来看一下有没有重复的计算。画一下 DP 数组可以发现,在 $dp[i + 1][j]$ 选 $k \geq 1$ 时描述的状态,和在 $dp[i + 1][j - w[i]]$ 选 $k - 1$ 描述的状态是一样的,再向前推也成立。前一个状态已经达到了最优,那么只需要把它拿过来加上一个 $w[i]$ 就行了(无后效性),毕竟只有这么一个转移的方向,$k$ 从 $0$ 开始的增长就可以简化到 $k = 0$ 或 $k \geq 1$,这和01背包是一个意思。

也可以看书上的数学证明:

这就是01背包了。如此可以舍去关于 $k$ 的循环,复杂度为 $O(nW)$。可以尝试用一维数组去解。

像01背包一样,也可以只用一维数组来做。注意此处每次转移依赖“这一行”的前项,要更改循环顺序。

完全背包 02

和同学讨论到的另一种经典的完全背包问题:

使用若干种给定面额的硬币搭配出指定总面额。每种面额的硬币不限枚数,求全部方案数。

定义 $dp[i + 1][j]:=使用前i种硬币搭配出总额j的方案数(可取0枚)$,则当允许取当前种的硬币时,总方案数等于“取它”和“不取它”的和,即 $dp[i + 1][j] = dp[i + 1][j - w[i]] + dp[i][j]$。每次更新要用到当前行的前项。

多重部分和

给定 $n$ 种不同大小的正整数,数字 $a_i$ 有 $m_i$ 个。判断是否存在一种选数方案,使选出的数字和恰为 $K$。

DP 数组的定义会影响复杂度。

有这样三种定义:

  1. $dp[i + 1][j]:=前i种数字能否加成j$
  2. $dp[i + 1][j]:=前i种数字加成j的方案数$
  3. $dp[i + 1][j]:=前i种数字加成j时,第i种剩余的个数$

1

要使前 $i$ 种能加成 $j$,则前 $i - 1$ 种要能加成 $j, j - a_i, \cdots j - m_i a_i$ 之一。开循环会有三层,复杂度 $O(K\sum_i m_i)$ ,容易炸。没有看到 $n$ 是因为它在求和里面。

2

和上文选硬币的方法一样。显然 $j < a[i]$ 时是不能选当前的。注意上界是 $\min(K,至今为止所有可选硬币的价值和)$,为了节省时间可以在读入的时候维护一个前缀和。最高复杂度 $O(nK)$。

3

注意不能加成 $j$ 的位置要用 $-1$ 填充。则 $dp[i][j]\geq 0$ 时,$dp[i + 1][j] = m_i$;$dp[i + 1][j - a_i] = k$ 时,$dp[i + 1][j] = k - 1$;$dp[i + 1][j - a_i] \leq 0$ 或 $a_i$ 选不上时,$dp[i + 1][j] = -1$。复杂度 $O(nK)$。

最长上升子序列 LIS

长度为 $n$ 的数列 $a_0, a_1, \cdots a_{n - 1}$,求它最长上升子序列的长度。

经典字符串题目。

定义 $dp[i]:=以a_i结尾的最长上升子序列的长度$,每次扫描到一个新字符,将它和之前的各字符比较,在比它小的字符里选出数组值最大的,加一作为新字符位置的值。没有更小的字符时,取零加一。同时维护整个数组至今的最大值即可。复杂度 $O(n^2)$。

或者定义 $dp[i]:=长度为i+1的上升子序列中最小的末尾元素$,这样定义的原因是相同长度的子序列,末尾越小,后续更有可能遇到更大字符。如果不存在一个长度的子序列,用充分大填充。显然这个数组除了充分大之外是递增的,可以用二分优化到 $O(n\log n)$。

计数问题的 DP

划分数

有 $n$ 个无区别的物品,将它们划分成不超过 $m$ 组,求出划分方法数。结果对 $M$ 取余。

比如 $4$ 个物品分成 $3$ 组以内,叫 $4的3划分$。注意每组是不分先后的,即 $1+1+2$ 和 $1+2+1$ 是同一种划分。DP 在解计数问题和期望问题时也经常用。

定义 $dp[i][j]:=j的i划分的总数$,则容易想到如果每组不同,则 $j$ 的 $i$ 划分就是先取出 $k$ 个,再计剩下 $j - k$ 的 $i - 1$ 划分,$k$ 从 $0$ 到 $j$。

每组相同时,要考虑重复计算,也不能单纯地把 $k$ 取 $0$ 到一半。考虑新的递推关系:当一个 $n$ 的 $m$ 划分 $\{a_i\}(\sum_1^m a_i = n)$ 成立时,考察它的每一项。如果各项为正,则它对应一个 $n - m$ 的 $m$ 划分;如果有为零的项,则它至少对应一个 $n$ 的 $m - 1$ 划分。此处“至少”是指推到上一个状态即可。则有以下递推关系:$dp[i][j] = dp[i - 1][j] + dp[i][j - i]$。处理一下边界,可以在 $O(nm)$ 里得到答案。

多重集组合数

有 $n$ 种物品,第 $i$ 种有 $a_i$ 个,不同种之间物品不同,同种之间无法区分。从这些物品中取出 $m$ 个,求取法总数对 $M$ 取余的结果。

比较方便地定义 $dp[i][j]:=从前i种物品中取j个的方案总数(模M)$。则 $dp[i][j]$ 是 $dp[i - 1][j - k]$,$k$ 从 $0$ 到 $\min(j, a_{i - 1})$。直接计算的复杂度是三次,再往回推一项之后合并,如下优化到二次:

注意分类讨论时的越界问题。优化的目的是化成递推。

这篇我好像拖了将近一个月?一做志愿者就废了……

下面讲数据结构。正好这学期也开这门课。

还想着看完这本书之后买块键盘呢……