AGC007F Shik and Copying String

题意：定义字符串的复制操作如下 ：

将字符串 复制得到 。则 ，且 ，而 或者 。

现在给出字符串 ，问 至少经过几次复制之后可以得到 。

，时限 。

---

首先特判 。

考虑 中的每个字符来源于 中的那个字符，表示对应关系的边是不会相交的，且一定是一个字符对应一个区间。

假设我们得知了对应关系和所需步数，那么可以采取这样的策略：先一直尽量右移，直到移动到需要覆盖的左边界处，然后向下到达底线，然后横向覆盖。（实际上就是让路径尽量靠右）

如图：

不难证明这是最优策略。

考虑我们得知了对应关系，如何得到最优步数。

我们从后往前考虑每个 中需要匹配的左端点，让路径尽量靠右，若目前的层数无法完成，则加一层。

具体地，用队列维护上一条路径的所有（右侧）转折点。这些转折点的横纵坐标都是单调增加的。

当 要前往 。

末端弹出（pop）那些横坐标在 后面的所有转折点。

然后，所有转折点都向左下方移动一位。

若起点衔接不紧密，则会新增（push）一个转折点。如图：

（深蓝色是上一条路径的转折点，深红色是新路径的转折点）

答案是所有转折点的纵坐标的最大值 。

若事先未给定匹配关系，从后往前考虑 ，贪心地选择 中能匹配的最靠右的字符即可。

复杂度为 。