首页 > 代码库 > 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 }
View Code

 

 

 

 

 

String painter (hdu 2476 DP好题)