posted on 2022-09-13 15:19:49 | under 题解 | source
problem
一个字符串 \(a\)，一开始全空，支持区间修改为同一字符，后修改的覆盖先修改的，求将字符串修改为目标字符串的最小操作次数。\(1\leq n\leq 50\)。
如：\(\tt abaca\) 可以在三步之内完成。
solution
我可以断言，在这些染色区间中，要么不交，要么完全包含，这总是可以调整的。
考虑令 \(f_{[l,r]}\)，考虑分类讨论：
- \(a_l=a_r\)：考虑在 \(f_{[l,r-1]}\) 的操作中，有一次形如 \([l,k]\) 的操作将 \(a_l\) 染色，那么我们可以将这次操作的 \(k\) 延长到 \(r\)，并把它扔到所有操作最前面，这样就有 \(f_{[l,r]}=f_{[l,r-1]}\)；
- \(a_l\neq a_r\)：染 \(a_l\) 和 \(a_r\) 这两步一定不交，可以分成 \([l,k_1]\) 和 \([k_2,r]\) 两步（\(k_1<k_2\)），于是枚举 \(k\) 在哪里并转移。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,f[60][60];
char a[110];
int dp(){
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;i++) f[i][i]=1;
for(int t=2;t<=n;t++){
for(int l=1,r=t;r<=n;l++,r++){
if(a[l]==a[r]) f[l][r]=f[l][r-1];
else for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
}
}
}
return f[1][n];
}
int main(){
scanf("%s",a+1),n=strlen(a+1);
printf("%d\n",dp());
return 0;
}
//abaca