程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 2476 String painter

hdu 2476 String painter

編輯：C++入門知識

String painter

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

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

Source 2008 Asia Regional Chengdu
題意：有兩個字符串長度相同，現在有一個painter，一次可以把第一個字符串中的一段區間內的所有字母都換成同一個字母（這個字母可以是任意一個），問最少執行多少次操作，才能將第一個字符串轉換成第二個字符串

思路：先將空白串變為s2，dp[i][j]-將i~j刷為目標串所需要的步數。 dp[i][j]=dp[i][j-1]+1; j單獨刷當s[j]==s[k]時，j可以借助刷k的時候一起刷，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);

然後後面的其實我也還不是太懂，先寫下來後面在慢慢看，區間dp還理解的不夠透徹。處理完前面的後後，我們就要看第一個字符串究竟需要噴刷多少次了，用res[i]記錄1-i區間第二個字符串得出的噴刷次數，如果第一個字符串的i位置與第二個字符串的i位置相同，那麼這個位置就不用噴刷了，res[i]=res[i-1],如果不相同，就要就要借助一個位於1-(i-1)區間內的變量來分割開

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 105
#define MAXN 100005
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot;
char s1[maxn],s2[maxn];
int dp[maxn][maxn],res[maxn];

int main()
{
    int i,j,t,k,len;
    while(~scanf("%s%s",s1+1,s2+1))
    {
        memset(dp,0,sizeof(dp));
        n=strlen(s1+1);
        for(i=1;i<=n;i++)
        {
            dp[i][i]=1;
        }
        for(len=2;len<=n;len++)
        {
            for(i=1;i<=n;i++)
            {
                j=i+len-1;
                if(j>n) break ;
                dp[i][j]=dp[i][j-1]+1;
                for(k=i;k