CF1132F Clear the String

Solution

区间 dp。设 $F_{l,r}$ 为删去区间 $[l,r]$ 的最小代价。显然，一个包含两种或以上字符的区间，它代价最小的删去方法中，一定存在一个断点将区间分成左右两半，使得这两个区间是各自删去的。

不妨令左半区间最后一次删除前， $S_l$ 未被删去；右半区间最后一次删除前， $S_r$ 未被删去。显然这样做不会使代价更坏。那么此时左半和右半区间分别都由相同的字符组成。如果 $S_l=S_r$ ，则左右区间的最后一次删除可合成一次执行。由此得到转移方程

$F_{l,r}=\min_{1\le k < r}\{F_{l,k}+F_{k+1,r}-(S_l=S_r)\}$

时间复杂度 $O(n^3)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 505;

int n, f[N][N];
char s[N];

int main()
{
    scanf("%d%s", &n, s + 1);
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n + 1; i++)
        f[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            for (int k = i; k < i + len - 1; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] - (s[i] == s[j]));
        }
    }
    printf("%d", f[1][n]);
    return 0;
}