标签：USACO19DEC min text Cost Cowmbat 字符串 rm Moortal dp

前言

很可惜, 离场切不远

多练练 \(\rm{dp}\) 吧

算法

简化题意

给定一长为 \(n\) 的字符串 \(S\) , 由前 \(m\) 个小写字母构成, 现在要求将这个字符串变换成一个由至少连续 \(k\) 个相同字符构成的字符串组成的字符串( 下称为 合法字符串 ), 其中, 字符 \(a \to b\) 的花费为 \(W_{a, b}\)

显然的, \(W_{a, b}\) 的计算可以用 \(\rm{Floyd}\) 进行 \(O(m^3)\) 的计算

考虑状态转移方程的设计

令 \(dp_{i, p}\) 表示字符串到 \(i\) 结尾时, 当前的结尾字符为 \(p\) , 令其为合法字符串的最小花费

令 \(Cost(S_{a, b} \to p)\) 表示将字符串从 \(a\) 到 \(b\) 染成颜色 \(p\) 的花费

则有

• 跟上之前的染色, 不需要考虑长度
• 自己单独拉出来进行染色, 长度至少为 \(k\)

\[\left\{ \begin{array}{lr} dp_{i, p} = \min\left[ dp_{j, p} + \rm{Cost} ( { S_{j + 1 \sim i} \to p })\right]\text{ }, \text{ } j < i \ , & \\ dp_{i, p} = \min\left[ dp_{j, q} + \rm{Cost} ( { S_{j + 1 \sim i} \to p } ) \right] \text{ }, \text{ } j \leq i - k \text{ } \end{array} \right. \]

分析 \(1\) 式

显然的, 一式完全可以转化成

\[dp_{i, p} =\rm{Cost}(S_{1, i} \to p) \]

这仅仅用于初始化, 可以不加关注

分析 \(2\) 式

观察到这个式子并不好转移 (如果有人可以提供直接转移的方法, 欢迎找我讨论)

但是我们观察到, 枚举当前的结尾字符是不必要的

我们每次转移计算 \(Cost\) 的时候, 完全只需要全部枚举一遍求最小即可, 压维

因此化简 (\(p\) 枚举可得)

\[dp_i = \min_{j = 1}^{i - k}(dp_j + \rm{Cost}(S_{j + 1 \sim i} \to p)) \]

---

总结一下, 问题转化成,

初始化 (枚举 \(p\))

\[dp_{i} =\rm{Cost}(S_{1, i} \to p) \]

递推

\[dp_i = \min_{j = 1}^{i - k}(dp_j + \rm{Cost}(S_{j + 1 \sim i} \to p)) \]

这个式子显然只需要记录一下前缀最小值即可 \(\mathcal{O}(1)\) 递推

总时间复杂度 \(\mathcal{O}(nm)\)

代码

略

总结

多练习 \(\rm{dp}\) , 能赢吗? 会赢的, 包赢的

不好转移? 考虑压维

标签：USACO19DEC,min,text,Cost,Cowmbat,字符串,rm,Moortal,dp
From： https://www.cnblogs.com/YzaCsp/p/18548644