首页 > 代码库 > HDU-2476 String painter

HDU-2476 String painter

2024-07-13 07:24:37   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=2476

                  String painter

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


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

题意：

给出两个串s1和s2，一次只能将一个区间刷一次，问最少几次能让s1=s2

例如zzzzzfzzzzz，长度为11，我们就将下标看做0~10

先将0~10刷一次，变成aaaaaaaaaaa

1~9刷一次，abbbbbbbbba

2~8:abcccccccba

3~7:abcdddddcba

4~6:abcdeeedcab

5:abcdefedcab

这样就6次，变成了s2串了

第二个样例也一样

0

先将0~10刷一次，变成ccccccccccb

1~9刷一次，cdddddddddcb

2~8:cdcccccccdcb

3~7:cdcdddddcdcb

4~6:cdcdcccdcdcb

5:cdcdcdcdcdcb

最后竟串尾未处理的刷一次

就变成了串2cdcdcdcdcdcd

所以一共7次

先是考虑将所有与目标字符串不相同的刷成目标串：

dp[i][j]表示刷i-j区间，

初始条件：dp[i][j]=dp[i+1][j]+1;

 

对于k=(i+1...j )如果str[k]==str[i],则dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]),,因为刷i的时候可以与k同时刷。

 

上面是对初始串与目标串完全不同的情况，

如果有部分的不同：

ans[i]表示将str1[0...i]刷成str2[0...i]的最小步数，

if  str1[i]==str2[i]  则ans[i]=ans[i-1];

else

   ans[i]=min(ans[i],ans[j]+dp[j+1][i])  j<i;

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int dp[105][105],ans[105];//dp表示从i到j刷的次数，ans表示从0到i刷的次数。int main(){    int k,i,j,g,len;    char str1[100],str2[100];    while(~scanf("%s%s",str1,str2))          {               len=strlen(str1);              //上面的初始化不行，下面初始化可以，我不太清楚原因，但是我在想初始化一定伴随更新。              /*for(j=0;j<len;j++)                for(i=j;i>=0;i--)                    {                     dp[i][j]=j-i+1;//初始化，每个字母都刷一遍。                   }*///这个是没用的初始化。              for(k=0;k<len;k++)                for(i=0;i<len-k;i++)                 {                      j=i+k;//控制i，j区间。                     dp[i][j]=dp[i+1][j]+1;//初始化，每个字母都刷一遍,先每个单独刷                         for(g=i+1;g<=j;g++)//i到j中间所有的刷法                           if(str2[g]==str2[i])//刷i的时候可以与k同时刷。                          dp[i][j]=min(dp[i][j],dp[i+1][g]+dp[g+1][j]);                          //i与k相同，寻找i刷到k的最优方案                   }                for(i=0;i<len;i++)                   {                        ans[i]=dp[0][i];//根据ans的定义先初始化                      }                for(i=0;i<len;i++)                  {                      if(str1[i]==str2[i])                          ans[i]=ans[i-1];//如果对应位置相等，这个位置可以不刷                        else                         {                            for(j=0;j<=i;j++)                            ans[i]=min(ans[i],ans[j]+dp[j+1][i]);//寻找j来分割区间得到最优解                         }                  }            printf("%d\n",ans[len-1]);          }    return 0;}/*zzzzzfzzzzzabcdefedcbaababababababcdcdcdcdcdcd */

 


联系
我们