# HDU 2476 String painter（区间DP）

String painter

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2792 Accepted Submission(s): 1272

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 <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>

using namespace std;
int dp[105][105];
int ans[105];
char s1[105];
char s2[105];
int main()
{
while(scanf("%s%s",s1+1,s2+1)!=EOF)
{
memset(dp,0,sizeof(dp));
int len=strlen(s1+1);
for(int j=1;j<=len;j++)
{
for(int i=j;i>=1;i--)
{
dp[i][j]=dp[i+1][j]+1;
for(int k=i+1;k<=j;k++)
{
if(s2[k]==s2[i])
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
}
}
}
for(int i=1;i<=len;i++)
ans[i]=dp[1][i];
for(int i=1;i<=len;i++)
{
if(s1[i]==s2[i])
ans[i]=ans[i-1];
else
{
for(int j=i-1;j>=1;j--)
ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
}
}
printf("%d\n",ans[len]);
}
return 0;
}```

0 条评论

## 相关文章

### HDU 5618 Jam's problem again（三维偏序，CDQ分治，树状数组，线段树）

Jam's problem again Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 655...

528160

### HOJ 2226&POJ2688 Cleaning Robot（BFS+TSP（状态压缩DP））

Cleaning Robot Time Limit: 1000MS Memory Limit: 65536K Total Submission...

30640

### POJ 2209 The King(简单贪心)

The King Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7499...

29140

364120

### POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

34870

### POJ-1125 Stockbroker Grapevine

Stockbroker Grapevine Time Limit: 1000MS Memory Limit: 10000K Total Sub...

31840

### HDUOJ-------（1022）Train Problem I

Train Problem I Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

31770

### HDU 5157 Harry and magic string(回文树)

Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

37580

### HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

37460

### HDUOJ---The Moving Points

The Moving Points Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/...

33540