HDU 2476 String painter(区间dp) - dblank

HDU 2476 String painter(区间dp)

Problem Description
There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?


Input contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.


A single line contains one integer representing the answer.


Sample Input
zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd


Sample Output
6 7
思路:学习了kuangbin大神的博客才理解的,就是先dp获得一个从空串获得b串的最小次数,这个地方,比如获得abcda的代价就是代价(bcd)+1,这里的1就是涂后面那个a的代价,因为可以一起涂成a,然后涂中间的,所以这里直接b[i] == b[k]的时候,区间dp一下。然后对a串到b串,如果a[i] == b[i],这个i位置我我们就可以不涂,这里也区间dp一下。
using namespace std;  
const double eps = 1e-10;  
const int inf = 0x7fffffff, N = 1e2 + 10;  
typedef long long ll;  
using namespace std;  
char s[N], x[N];  
int dp[N][N], ans[N];  
int main()  
    while(~scanf("%s%s", s, x))  
        int len = strlen(s);  
        memset(dp, 0, sizeof(dp));  
        for(int i = 0; i<len; i++)  
            for(int j = i; j<len; j++)  
                dp[i][j] = j - i + 1;  
        for(int i = len - 1; i>= 0; i--)  
            for(int j = i + 1; j<len; j++)  
                dp[i][j] = dp[i+1][j] + 1;  
                for(int k = i + 1; k<=j; k++)  
                    if(x[i] == x[k])  
                        dp[i][j] = min(dp[i][j], dp[i+1][k-1]+dp[k][j]);  
        for(int i = 0; i<len; i++)  
            ans[i] = dp[0][i];  
            if(s[i] == x[i])  
                if(!i) ans[i] = 0;  
                else ans[i] = ans[i-1];  
            for(int j = 0; j<i; j++)  
                ans[i] = min(ans[i], ans[j] + dp[j+1][i]);  
    return 0;