首页 > 代码库 > String painter (hdu 2476 DP好题)
String painter (hdu 2476 DP好题)
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2476
题目大意：
给出两个等长的串S, T, 要将S变成T, 每次可以把S的连续的一段变成相同的字母,求最少操作数。
这题网上看了好多题解,理解了好久, 记录一下我的理解吧。
首先求出把空串变成T的最少次数。
dp[i][j] 表示把空串变成T[i ... j]的最少次数。
首先dp[i][j] = dp[i + 1][j].
然后有一个性质。如果两次染色的区间有交, 那么小的区间一定完全包含于大的区间(左右端点也不会重合), 且一定是大区间 在小区间之前染色(否则 小区间完全被覆盖 就没用了)。
如果不是这样, 可以改造一下区间 变成这样。
所以第一次染色 一定是[i, k], 然后T[k + 1, j]可以单独考虑(因为染色不能再和[i, k]有交了)。
那么如何选这个k呢？
只要考虑T[i] = T[k]的位置, 如果不是,可以调整染色区域长度 变成右端点的颜色和 T[i]一样。
然后有另外一个性质：
如果T[i] = T[j], dp[i][j] = dp[i + 1][j]. 只要第一次染色区域选择[i, j], 就可以和dp[i + 1][j] 对应起来。
综上 dp[i][j] = min{dp[i + 1][j] + 1, dp[i + 1][k] + dp[k][j] (T[i] == T[k]) }
最后根据dp数组再做一次DP。
ans[i] 表示考虑S[1 ... i] T[1 ... i]
如果S[i] == T[i] 显然ans[i] = ans[i - 1]
否则肯定有一段S的区间[k ... i] 都被刷子刷过。 那么这一段的情况就是dp[k][i].
所以ans[i] = min(ans[k] + dp[k + 1][i]).
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <cmath> 7 #include <map> 8 #include <queue> 9 #include <set>10 using namespace std;11 12 #define X first13 #define Y second14 #define N 11015 #define M 50001016 17 typedef long long ll;18 const int INF = 1 << 30;19 const int Mod = 1000000007;20 21 char s[N], t[N];22 int dp[N][N], ans[N];23 24 int main()25 {26 //freopen("in.in", "r", stdin);27 //freopen("out.out", "w", stdout);28 29 while (scanf("%s %s", s + 1, t + 1) != EOF)30 {31 int n = strlen(s + 1);32 for (int i = 1; i <= n; ++i) dp[i][i] = 1;33 for (int len = 2; len <= n; ++len)34 {35 for (int i = 1; i + len - 1 <= n; ++i)36 {37 int j = i + len - 1;38 dp[i][j] = dp[i + 1][j] + 1;39 for (int k = i + 1; k <= j; ++k) 40 if (t[i] == t[k]) dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);41 }42 }43 ans[1] = (s[1] != t[1]);44 for (int i = 2; i <= n; ++i)45 {46 if (s[i] == t[i]) ans[i] = ans[i - 1];47 else48 {49 ans[i] = dp[1][i];50 for (int k = 1; k < i; ++k) 51 ans[i] = min(ans[i], ans[k] + dp[k + 1][i]);52 }53 }54 printf("%d\n", ans[n]);55 }56 57 58 return 0; 59 }
String painter (hdu 2476 DP好题)