1. 前言
2. P1944 最长括号匹配
3. P1854 花店橱窗布置
4. P4310 绝世好题
5. CF41D Pawn
6. CF985E Pencils and Boxes
7. P1736 创意吃鱼法
8. P4059 找爸爸

前言

这里是某人的做题计划 - 动态规划专题题单的做题记录, 含有我对这些题目的原创思路, 因为做这些题时没有查看题解, 这里有些思路可能不完整或不正确, 但通过后一定会修正

P1944 最长括号匹配

思路: 在此题中, 我们存储的数据有两个, 即子串 ( 指括号匹配子串, 下同 ) 的长度, 子串的左端点或右端点, 这样我们才能确定唯一的一个子串, 也方便输出; 同时观察数据范围也可知算法时间复杂度必须为量级, 一般来说必须是一维 DP

状态定义: 定义为以结尾的最长子串长度, 这样是容易转移的

状态转移方程:

• 定义表示原字符串, 显然当是一个左括号时不可能作为一个子串的结尾, 为 0
• 否则, 查询, 判断该括号能否和匹配, 这样就跳过了中间已经合法的部分
• 若匹配成功, 查询, 加上这一对括号之前的子串长度 ( 由题意, 子串可以拼接 )

综上得到状态转移方程, 定义是一个返回 0 和 1 的函数, 代表, 两个字符是否是匹配的括号

边界条件: 全部初始化为 0 即可

P1854 花店橱窗布置

思路: 在题目所给的表格中进行模拟, 容易发现类似于在表上取数, 可以从左上方走来 ( 插花了, 或者理解为选当前数 ), 也可以从左边走来 ( 不插花, 不选当前数 ) , 数据范围也允许二维 DP

状态定义: 定义为走到点时能取到的最大价值

状态转移方程: 定义价值矩阵为, 显然有

同时因为不可能插的花比花瓶还多, 所以如果, 直接跳过

边界条件: 因为存在负值, 所以初始化为负无穷, 只有时为 0

P4310 绝世好题

思路一: 时间复杂度为的写法是比较好想的, 设原序列为, 定义表示以结尾的子序列的最大长度, 因为是子序列而非子串, 所以每次暴力枚举接在哪里, 进行转移即可

思路二: 由于数据范围显然不允许思路一中的算法通过, 考虑与运算的特殊性质, 若两个数的二进制表示中有任意一位都为 1 , 则结果非 0 , 则我们可以想到另一种状态定义, 不记录每个数对应的子序列的最大长度, 而是记录每一个二进制位, 对于所有这一二进制位为 1 的数, 以这些数为子序列的结尾所取得的最大长度

状态定义: 如思路二所言, 定义为所有满足且的为结尾的子序列的最大长度

状态转移: 此状态看似不好转移, 但其实还算容易想, 考虑对于任意一个数, 它可以接到任何一个与它有至少一个相同二进制位的数上, 并作为结尾继续转移, 因此想到将对原数组的遍历作为外层循环 ( 当前遍历到的数表示为 ) , 同时对于有

每次先计算其中第二个最大值, 再计算第一个, 即可完成转移

边界条件: 最大值最小为 1 , 初始设为 1 即可

CF41D Pawn

思路: 考虑弱化的版本, 若没有倍数限制, 显然可以使用二维 DP 解决, 那么若有限制, 只需再加一维记录这个限制即可; 具体来说, 加上一维代表当前取到的豌豆数, 将 DP 变成可达性 DP , 豌豆数最大不超过 1000 , 因此可以开下

状态定义: 定义为当前在点, 能否取到个豌豆

状态转移: 设代表豌豆数的矩阵, 比较容易得到

边界条件: 注意当时要求且当时要求, 要倒序遍历, 遍历时要求, 初始值将这一行全部赋值为 true 即可

CF985E Pencils and Boxes

思路一: 不要求保持原顺序 ( 否则就很简单了 ) , 将原序列排序后显然是最优的, 因为若交换两个数, 相当于将其中一个减少, 另一个增加, 对于任意两个不以这两个数为其中一端的段, 其中一段差不变, 而另一段差必定变大, 不如排序后优

思路二: 输出有没有解, 考虑可达性 DP , 由数据范围可知只能允许一维 DP , 通常的写法应该是记录以某个点为结尾合不合法

状态定义: 定义为原序列的前个元素能否构成满足条件的分组方案

状态转移: 根据边界条件容易得到 ( , , 含义见题面 )

但这样会超时 ( 时间复杂度是的 ) , 考虑如下优化

• 的值随着的增大单调不减, 因此一旦不合法, 可以退出循环
• 由于是直接赋值, 所以已经更新过的不必再更新, 即每次将赋值为 true 时, 下次循环最劣也从开始, 而非

这样每个位置最多更新一次, 复杂度均摊, 可以通过

边界条件: 注意, 我们只知道一定为 true , 其它均不能保证, 且在遍历时当走到时, 只有以前的值不可能再被更新; 其余值全部赋值为 false 即可

P1736 创意吃鱼法

思路一: 根据数据范围容易得到大概是二维 DP , 通常的写法应该是记录以某个点为左下角 ( 其它角也可以, 下同 ) 的子矩阵中的最大值

思路二: 对角线不好统计, 考虑拍扁成子矩阵的边, 因为是方阵, 边长和对角线长是一样的, 因此只要存储最大的符合条件的子矩阵的边长即可

状态定义: 定义为以为左下角的所有符合条件的子矩阵中, 最大一个的边长

状态转移: 若的值为, 其含义代表了从点向上个单位, 向左或向右个单位, 都没有 1 , 归纳法可知, 每次只要判断当前向上个单位, 向左或向右个单位, 都没有 1 即可, 每次从左上或右上转移来, 具体实现见下面状态转移方程

令, , 分别为向上, 向左, 向右极长的连续 0 段的长度, 则有

边界条件: 数组赋值为原数组, 遍历时, 只遍历为 1 的点即可; 求得, , 注意控制边界; 答案在数组中的最大值取得, 在转移时顺路求一下就行

P4059 找爸爸

思路一: 首先将题目弱化, 不考虑空格对相似程度的影响, 这题就和最短编辑距离很像, 由于只有都不是空格的时候距离才有定义, 加上一维表示空格状态, 0 代表都没有空格, 1 代表 A 串此时末尾有空格, 2 代表 B 串此时末尾有空格, 如果两个串末尾都有空格, 那么删掉这两个空格显然是更优的

思路二: 想到对式子本身进行分解, 其含义相当于, 每进入一个空格段, 相似程度减去, 以后每再多加一个空格, 相似程度再减

状态定义: 定义表示 A 串处理了个字符, B 串处理了个字符, 空格状态为的最大相似程度

状态转移: 显然有 ( , , 含义见题面 )

边界条件: 首先, 可能出现负值, 因此全部初始化为负无穷, 赋值为 0 ; 其次, 由于可能一个字符也还没处理, 所以遍历要从 0 开始, 而不是 1 , 边界注意判一下, 不要越界; 还有, 如果你对生物比较熟悉, 注意, 这题的顺序是 ATGC , 而不是通常的 ATCG