Stamp

作者 : 周子鑫

关键词 : 动态规划

题目简述

给定一个长度为$n$的串, 包含$\{R, G, B, *\}$ 4种字符的串$S$，你需要把一个长度为$n$的空白纸带给染成$S$。

$S$中的$*$符号可以匹配${R, G, B}$任意一种颜色。

染色定义为两个操作：

• 选择一个长度$L$，$L$一旦确定就不能更改。
• 在$\{R, G, B\}$ 三种颜色中选择一种，并在纸带上选择一段长度为$L$的空白区间，将这个区间颜色染成选定的颜色。这个操作可以进行若干次，直到纸带上每个位置都被上色。

假设进行了$K$次给长度为$L$的空白区间染色，染色的花费定义为$K * pushCost + L * stampCost$。

求把空白纸带染成$S$的最小花费。

$n \le 50$

分析

这题似乎也没什么性质（？）那么就先来考虑$L$确定的情况。

需要最小化$K * pushCost$, 那么就是要最小化$K$。

如果两两染色之间都没有覆盖，那么直接扫一遍判断是否合法就行了。问题是两染色之间可能会相互覆盖，这时候发现如果两次染色有覆盖，那么这两次染色所选的颜色肯定是相同的。

那么在纸带上，一段相同颜色区间的长度就至少为$L$.

诶..既然已经知道这个东西了，看起来就可以做了。

算法

首先当然是枚举这个长度$L$,然后考虑怎么去做算固定长度的情况。

下面介绍两种$dp$的思路

动态规划1

令$f[i]$表示前$i$个位置都与$S$匹配的最小染色数。 枚举这一段颜色的长度$X$, 其中 $X \ge L$,

$f[i] = min \left \{ f[i - X] + \left \lceil \frac{X}{L} \right \rceil \right \}$

这个还是非常好理解的，每一段长度为$X$的区间需要至少$\left \lceil \frac{X}{L} \right \rceil$次染色才能完成。

这种$dp$方法的时间复杂度是$O(n ^ 2)$

动态规划2

令$R[i]$表示前$i$个位置都合法且最后一次染了$R$的方案数, $G[i]$和$B[i]$同理。枚举上一次染色的区间，上一次染色的区间有两种可能：

• 上一个区间不和$[i - L, i]$相交，这种情况就直接$O(1)$转移就可以了。
• 上一个区间和$[i - L, i]$相交于$j$，我们已经知道，两个区间如果相交那么它们的颜色一定相同，以$R$为例 $R[i] = min \left \{ R[j] \right \} + 1$。

第二部分转移如果直接枚举所有的$j$，$dp$的复杂度就是$O(n ^ 2)$, 如果用单调队列去维护的话复杂度就是$O(n)$。

两种方法的空间复杂度都是$O(n)$。

将上述$dp$结合枚举$L$，总的时间复杂度就是$O(n^3)$或$O(n^2)$。