String painter
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2068 Accepted Submission(s): 908
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?
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.
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
abcdefedcba
abababababab
cdcdcdcdcdcd
Sample Output
6
7
7
Source
Recommend
lcy
题目描述 ： 给定一个初始串，目标串，每步可以通过改变一个连续的子串使其变为同一个字母，至少需要多少步？
我们发现一段序列，每一步的选择是可以改变任意长度的连续子串，
那么通过枚举改变哪些连续子串，可以包含所有的情况。
d[i]表示以i结尾的序列变成目标串需要的最少步骤。d[i]=min(d[i],d[k]+dp[k+1][i]),因为是[k+1,i]区间是连续改变的，
那么我们可以将dp[k+1][i]看成是表示[k+1,i]区间内一个相同串到目标串的最少步骤(刷[k+1,i]区间内的字符串,使这段连续的子串变为同一个字母).
初始化dp[i][i]=1;
dp[i][j]=dp[i][j-1]+1;
if(a[i]==a[k]) //有相同的连续改变才会有作用，不同，无论通过何种方式.每一个都需要改变，改变次数都一样
//相同的话，通过连续改变，可以减少改变次数，
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);
初始化d数组为0,d[i]=dp[0][1];
d[i]=min(d[i],d[k]+dp[k+1][i-1]);
通过枚举改变的连续子串的长度
动态规划： 定义状态，每一步的选择，包含了所有的可能性
最优子结构无后效性，如果状态设计不合理，会导致有后效性。
最优子结构无后效性，如果状态设计不合理，会导致有后效性。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[],b[];
int dp[][],d[];
int Length;
void init()
{
memset(dp,,sizeof(dp));
memset(d,,sizeof(d));
for(int i=;i<Length;i++)
dp[i][i]=; }
void solve()
{
/* for(int i=0;i<Length;i++)
for(int j=0;j<Length;j++)
for(int k=i;k<=j;k++)
{
dp[i][j]=min(DP(dp[i][k]+dp[k+1][j]),dp[i][j]);
}
for(int s=0;s<Length;s++)
{
for(int j=0;j<Length;j++)
printf("%d ",dp[s][j]);
printf("\n");
}
printf("2\n");
printf("%d\n",dp[0][Length-1]);
*/
for(int t=;t<Length;t++)
for(int i=;i<Length;i++)
{
int j=i+t;
if(j>=Length)
break;
dp[i][j]=dp[i][j-]+;
for(int k=i;k<j;k++)
{
if(b[k]==b[j]) //如果目标串有相同的，就可以一同处理
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j-]);
}
} for(int i=;i<Length;i++)
d[i]=dp[][i];
for(int i=;i<Length;i++)
{
if(a[i]==b[i])
d[i]=d[i-];
else
{
for(int k=;k<i;k++)
d[i]=min(d[i],d[k]+dp[k+][i]);
} }
}
int main()
{
//freopen("test.txt","r",stdin);
while(~scanf("%s%s",a,b))
{
Length=strlen(a);
init();
solve();
printf("%d\n",d[Length-]);
}
return ;
}