题目概述
给定字符串 \(A\) 和字符串 \(B\)，定一次操作为将 \(A\) 一个区间的字符全部换成同一个，问最小操作让 \(A\rightarrow B\)。
分析
一看完题目感觉似曾相识，好像有道题目类似吧。
就这道：P4170 [CQOI2007] 涂色。
这道一开始 \(A\) 是全部为空的，这题显然难了一点。
首先考虑全为空，这个直接用区间 \(dp\) 可以直接解决。
接下来考虑怎么从 \(A\rightarrow B\)，我们可以考虑进行一个一段一段的 \(dp\)，即设 \(g_i\) 表示解决完 \([1,i]\) 的最小代价。
转移就是枚举 \([j+1,i]\) 是要使用操作的，因此有 \(g_i\leftarrow g_j+f_{j+1,i}\)，其中 \(f\) 是上面的那个区间 \(dp\) 所求。
这道题目就被优雅解决了。
代码
时间复杂度 \(\mathcal{O}(n^3)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 105
using namespace std;
char a[N],b[N];
int f[N][N],g[N];
signed main(){while(~scanf("%s%s",a + 1,b + 1)) {int n = strlen(a + 1);for (int i = 1;i <= n;i ++)for (int j = 1;j <= n;j ++) f[i][j] = 2e9;for (int i = 1;i <= n;i ++) f[i][i] = 1,g[i] = 2e9;for (int len = 2;len <= n;len ++)for (int i = 1;i + len - 1 <= n;i ++) {int j = i + len - 1;if (b[i] == b[j]) f[i][j] = f[i + 1][j];elsefor (int k = i;k < j;k ++) f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j]);}for (int i = 1;i <= n;i ++) {if (a[i] == b[i]) g[i] = g[i - 1];elsefor (int j = 0;j < i;j ++) g[i] = min(g[i],g[j] + f[j + 1][i]);}printf("%lld\n",g[n]);}return 0;
}