动态规划汇总3

北斗七星 · 2022-01-15 10:04:08 · 个人记录

动态规划汇总3

题目：P3176 [HAOI2015]数字串拆分

解答：

• 设 F_i 表示 f_i 对应的矩阵，a 为转移矩阵，则 F_i=F_1a^{i-1} ，发现 a[1][1]=1=f_1 ，将 f_1 赋值为 a，则 F_i=a^i
• F_{a+b}=F_aF_b
• 设 A_{l,r} 表示 s_0 的 [l,r] 所组成的数对应的矩阵，可以发现 A_{l,r}=A_{l,r-1}^{10}\times F_{s_r}
• 设 dp_i 为 [1,i] 组成的数的答案 g，枚举上一个位置 j， O(|s|^2) 转移即可

题目：P4363 [九省联考 2018] 一双木棋 chess

解答：

• 每种可行的情况一定是单调不增的
• 用 0 表示往下走，1 表示往左走，从右上角到左下角的路径就可以被刻画出来

* * _
* _ _  --> 101001
* _ _

• 共 O(2^{2n}) 种情况
• 加一个数相当于 10 变为 01 ， \text{状压DP} 即可

题目：P3943 星空

解答：

• 异或差分，将区间修改变成双点修改
• 双点修改转化为单点移动，最后需要移动到某位置而抵消
• 设 f_{i,j} 为 i 与 j 抵消的代价，可以用最短路求出
• 点数少， \text{状压DP} 暴力转移

双倍经验：CF79D Password

题目：P2167 [SDOI2009]Bill的挑战

解答：

• 题目要求“刚好”，所以要找到所有满足条件的字符串
• 记 num_{i,ch} 第 i 位能与 ch 匹配的字符串集合
• 设 f_{i,s} 表示 s 集合中的字符串前 i 位都匹配的方案数，那么 f_{i,s}\rightarrow f_{i+1,s\cap num_{i+1,ch}}，答案为 \sum f_{n,s}

题目：P1777 帮助

我的解法：

• 分类选不选，从而计算代价

6 1
27 26 28 25 26 26

对于上面的样例，26 移到后面，最小代价为 4，但我的答案是 5，没有考虑移动到后面的情况，不过题目若是只能往前移就是对的了

正解：

• 将调整看为删除来做
• 最后再将选的插进来，放在同样的数旁边不会产生新的代价，所以加上全部选走的个数就好了

题目：P6622 [省选联考 2020 A/B 卷] 信号传递

解答：

• 可以记录 i 转到 j 的次数，推出 i 与 j 先后关系所对应的代价
• f_{i,j,s} $ 表示 i 位置上为 j 且前 i 位总状态为 s 的代价最值，则有$ f_{i,j,s}=\min{ f_{i-1,?,s-j}+g_{j,s-j}}
• 发现 s 的位数是 i，去掉第一维，将 s 按位数顺序转移，变为 f_{j,s}
• 设 F_s=\min{f_{j,s}} ，那么 f_{j,s}=F_{s-j}+g_{j,s-j} ， O(n2^n) 的复杂度

题目：P5363 [SDOI2019]移动金币

解答：

• 反面考虑，按位考虑，记 f_{i,j} 表示选完了 i 个 0，j 个位异或为 0 的方案数， f_{i,j} \leftarrow f_{i-k\times 2^{j-1},j-1}\times \binom{\lceil \frac{m}{2}\rceil}{k}
• 最后插板计算，总和减去异或为 0 的方案数即可

题目：CF1654G Snowy Mountain

解答：

• 将每个点 u 的高度 g_u 求出
• 点 v 有相邻的等高点，则点 u 的贡献为 2g_u-g_v ，希望 g_v 最小
• 高度为 k 的有相邻的点，会占 2k ，所以高度种类数为 O(\sqrt n)
• 高度排序，树形 \text{DP} 求解 点 u 最小 的 g_v

题目：CF778E Selling Numbers

解答：

• 设 dp_{i,s} 表示处理到第 i 位，后缀前 s 大的数有进位的最大价值， dp_{i,s} \rightarrow dp_{i+1,s'}
• 枚举最后的进位状态 s，处理高位
• 后缀排序 O(n^2) ，动态规划 O(n^2) ，注意细节

题目：CF506E Mr. Kitayuta's Gift

解答：

• 记 f_{i,j,k} 表示由 s[j,k] 加新字符构成的半径长度是 i 的回文串个数，在 i 一定的情况下，为了防止算重，钦定先选原串能匹配的
• 如果 s_j=s_k ，那么 f_{i,j,k}=25f_{i-1,j,k}+f_{i-1,j+1,k-1}
• 如果 s_j\neq s_k ，那么 f_{i,j,k}=24f_{i-1,j,k}+f_{i-1,j+1,k}+f_{i-1,j,k-1}
• 发现都是从 i 转移到 i+1 去的，将 j 与 k 的加减看作走动，直着走的视为红点，斜着走的视为绿点

• 题目转化为路径长度为 \lceil \dfrac{n+|S|}{2} \rceil 的个数
• 可以发现，当红点有 k 个时，有 \lceil \dfrac{|S| -k}{2} \rceil 个绿点
• 由于红绿点的形式相同，对于一条路径，只与红绿点的个数有关，与排列方式无关
• 因为终点前面的点是绿点，所以可以将一条合法路径重排，以先红后绿的方式排列
• 共有 O(|S|) 种本质不同的路径，我们希望可以继续合并路径
• 记 g_{i,l,r} 为到 [l,r] 的点经过 i 个红点的路径数，可以用记忆化搜索在 O(|S|^3) 的时间复杂度下求出
• 对于每一个终点前的绿点 [x,x] ，将 g_{i,x,x} 的贡献加给红点到绿点的路径上，来压缩路径

• 最后转化成新图上从起点到终点走 \lceil \dfrac{n+|S|}{2} \rceil 步的方案数
• 矩阵乘法加速 \text{DP} ，开始矩阵是单位矩阵，转移矩阵是邻接矩阵