题目：String painter
题意： 给出两个字符串A,B(长度相等) 现在可以执行的操作是，随便选一个区间， 将这个区间的字母全部变成 c (c是指a~z里面的任意一个字母) 问要将A串变成B串的最少操作次数
分析：
单纯的直接用区间dp不好状态转移，因为将区间[l,r[刷过之后，
改变了A串之后A串和B串的匹配情况不好考虑
所以区间DP的时候先不考虑A串与B串匹配的情况 dp[i][j]表示将区间[i,j]变得一样所需的最少操作次数 边界：if (i>j) return 0; 考虑从dp[i+1][j]转移到dp[i][j],安排第i个字符如何变 1.单独刷第 i 个字符 dp[i][j] = dp[i+1][j] +１; 2.从[i+1,j]中找到k满足 b[i] == b[k] dp[i][j] = dp[i+1][k] + dp[k+1][j] 也就是说，第i个字符因为要刷得和第k个一样 干脆刷区间[i+1,k]的时候一并刷了 DP跑出来之后考虑利用A串和B串匹配的情况 f[i]表示将A串的前i个字符变成与B串相同所需的最小操作数 if a[i] == b[i] f[i] = f[i-1] else 对区间[0,i-1]内的j f[i] = min(f[i],f[j] + dp[j+1][i]) 也就是先把前j个字符变得相同，然后让[j+1,i]完全不利用A、B的特性去刷 为什么可以，因为j枚举了区间[0,i-1]的所有值，这保证了没有漏解 取最小值则保证最优解
#define mem(a,x) memset(a,x,sizeof(a)) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; /* 题意： 给出两个字符串A,B(长度相等) 现在可以执行的操作是，随便选一个区间， 将这个区间的字母全部变成 c (c是指a~z里面的任意一个字母) 问要将A串变成B串的最少操作次数 分析： 先不考虑利用A串与B串相等的情况 dp[i][j]表示将区间[i,j]变得一样所需的最少操作次数 边界：if (i>j) return 0; 考虑从dp[i+1][j]转移到dp[i][j],安排第i个字符如何变 1.单独刷第 i 个字符 dp[i][j] = dp[i+1][j] +１; 2.从[i+1,j]中找到k满足 b[i] == b[k] dp[i][j] = dp[i+1][k] + dp[k+1][j] 也就是说，第i个字符因为要刷得和第k个一样 干脆刷区间[i+1,k]的时候一并刷了 DP跑出来之后考虑利用A串和B串相等的部分的情况 f[i]表示将A串的前i个字符变成与B串相同所需的最小操作数 if a[i] == b[i] f[i] = f[i-1] else 对区间[0,i-1]内的j f[i] = min(f[i],f[j] + dp[j+1][i]) 也就是先把前j个字符变得相同，然后让[j+1,i]完全不利用A、B的特性去刷 为什么可以，因为j枚举了区间[0,i-1]的所有值，这保证了没有漏解 取最小值则保证最优解 */ const int N = 111; char a[N],b[N]; int dp[N][N]; int DP(int i,int j) { if (i>j) return 0; if (~dp[i][j]) return dp[i][j]; dp[i][j] = DP(i+1,j)+1; for (int k = i+1;k <= j;++k) { if (b[i] == b[k]) { dp[i][j] = min(dp[i][j],DP(i+1,k)+DP(k+1,j)); } } return dp[i][j]; } int f[N]; int main() { while (~scanf("%s%s",a,b)) { int n = strlen(a)-1; mem(dp,-1); for (int i = 0;i <= n;++i) f[i] = DP(0,i); for (int i = 0;i <= n;++i) { if (a[i] == b[i]) f[i] = i?f[i-1]:0; else { for (int j = 0;j < i;++j) { f[i] = min(f[i],f[j]+DP(j+1,i)); } } } Pintc(f[n],'\n'); } return 0; }