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
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.

Output
A single line contains one integer representing the answer.

Sample Input
zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd

Sample Output
6 7

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
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]);
}
cout<<ans[len-1]<<endl;
}
return 0;
}