题意
给定两个长度相等，只有小写字母构成的字符串s和t，每步可以把s的一个连续子串“刷”成同一个字母，问至少多少步才能把s变成t。
思路
两层区间DP。
首先忽略原始串s，只去看目标串t，设dp1[i][j]表示从什么都没有的情况下利用刷子规则构造出目标串t的i到j这一段所需要的最小操作次数。这里着眼于“最后一次操作”进行阶段的划分。
dp1的状态转移：
- dp[i][j] = dp[i+1][j ] + 1
先默认最后一次操作是只刷出最新那个字符。 - 令k是i和j中间的某个位置，t是目标串，如果t[i] == t[k]
尝试用dp[i+1][k] + dp[k+1][j]更新dp[i][j]
因为i处字符等于k处字符，在构造i+1到k这个区段的时候，可以在刷k处字符的同时“顺便”把i位置也给刷了。
注意这里不可以写成dp[i+1][k-1] + 1 + dp[k+1][j]，考虑反例” /e(i对应)/ee/e(k对应)/… “,在这里dp[i+1][k-1]是1，用这种错误的算法dp[i][k]部分会变成2，但实际上应该是1。
接下来引入原始串s，令dp2[i]表示把原始串1到i构造成目标串1到i的部分所需要的最小的操作次数。这里有状态转移：
- 默认dp2 = dp1[1][i]
- 如果s[i] == t[i]
尝试dp2[i] = dp2[i-1]
否则尝试dp2[i] = dp2[i-1] + 1这里的意思是如果在第i位两个串对应字符相等，可以选择无需对这一位进行操作
- 令k是1到i之间的位置
尝试dp2[i] = dp2[k-1] + dp1[k][j]这里的意思是假设最后k位使用不考虑原始状态的构造方法，前面继承最优解。为什么要这样做？考虑fabcf这样的区间，一种较好的策略是先都刷成f，然后分别刷好abc，如果你选择这么做了，相当于已经无视了原来串的样子，因为第一步已经将全部中间字符都刷成f了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int dp[105][105]; int res[105]; int main(){ string a,b; while(cin >> a >> b){ memset(dp,0,sizeof(dp)); memset(res,0,sizeof(res)); int n = (int)a.size(); for(int i = 1;i <= n;i++){ dp[i][i] = 1; } for(int i = n-1;i >= 1;i--){ for(int j = i+1;j <= n;j++){ dp[i][j] = dp[i+1][j] + 1; for(int k = i+1;k <= j;k++){ if(b[i-1] == b[k-1]){ dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } } } } for(int i = 1;i <= n ;i++){ res[i] = min(dp[1][i],res[i-1]+(a[i-1] != b[i-1])); for(int j = 1;j <= i;j++){ res[i] = min(res[i],res[j]+dp[j+1][i]); } } cout << res[n] << endl; } return 0; } |
