线头 dp

感觉挺神奇的。

不知道该写什么，不如直接看题。

loj #2687. 「BalticOI 2013」Vim

首先可以发现删掉在位置 $i$ 的 e 有且仅有一种方式，就是走到 $i+1$ 并花费 $1$ 的代价走到 $i$，再花费 $1$ 的代价把 e 删掉，最后光标再次回到原来的 $i+1$。

所以我们可以直接把题意转化成：

给定一个字符串和一个集合，你可以在上面移动（移动规则同原题），求到达集合里面所有位置的方案中的代价最小值。

我们把从 $i$ 跳到 $j$ 看成一条线段，这样我们的移动轨迹就是一条折线，端点是停留的位置。

线头 dp 就是处理这种看着不好定转移顺序的折线的东西的，具体来讲，我们从前往后考虑折线，假设考虑到 $i$，我们把所有跨过 $i$ 的线段全部记录下来（一般来说我们可以发现一些良好的性质，使得记录的复杂度不是很大），然后考虑怎么更新到 $i+1$（一般来说是考虑线段是继续延伸还是止步于此）

可以发现一个很神奇的东西，这种情况是不存在的：


他是劣于这个的：


所以我们发现经过 $i$ 到 $i+1$ 这一段的线段数只可能是 $1$ 或 $3$，其中 $1$ 是操作 f，$3$ 是两个操作 f 和一个操作 h。（这里考虑 $i$ 到 $i+1$ 这一段是因为我们可以把）

有了这个，我们就可以在 $O(|S|^2)$ 的复杂度内记录下来所有跨过 $i$ 到 $i+1$ 这一段的线段了。