AT_abc325_g offence 题解

一道不难但是需要想一想的区间 DP。

有一个比较复杂的例子：ooofofxxx，简单的分析可知，一个 of 后面删除多少，与其前、后都有关，于是考虑区间 DP。

想到这里，其实问题已经解决一半了。

状态设计

设 \(f(l,r)\) 为闭区间 \([l,r]\) 经过操作之后的最小长度。

注意：我的状态设计与 官方题解 的区别在于，我设计的是闭区间，而官方题解是左闭右开。

考虑转移，我们分类讨论第一个字符是否删除。

删除

条件：

• \(S_l=\texttt{o}\)；
• 找到一个 \((l,r]\) 内的 \(k\)，满足 \(S_k=\texttt{f}\)；
• \((l,k)\) 内的所有字符能删除，即 \(f(l+1,k-1)=0\)。

转移：

• 那么可以转移 \(f(l,r)=\max\{f(k+1,r)-K,0\}\)；
• 表示：先删除 \((l,k)\)，然后删除 \(l\) 和 \(k\) 及后面的 \(K\) 的字符，但是不能删到负数。

不删除

条件：

• 无，任何情况均可转移.

转移：

• 因为第一个字符不删除，所以 \(l\) 和 \((l,r]\) 是独立的；
• 所以有 \(f(l,r)=f(l+1,r)+1\)；
• 表示：\(l\) 后面的，最少可以剩下多少个字符，在加上 \(l\) 这个字符。

代码

于是，时间复杂度为 \(\mathcal{O}(n^3)\)，可过。

代码见：https://atcoder.jp/contests/abc325/submissions/46904975