HDU 2476 String painter 區間DP

String painter

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2890    Accepted Submission(s): 1319

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  

Recommend lcy

    又是一道費腦DP。。。

    dp[i][j]表示将一個空白字元串的[i,j]區間刷為與str2的[i,j]區間相同所需要的最少次數。

    首先，我們能夠知道dp[i][j]=dp[i+1][j]+1，因為假設str1為空串，是以每一個字元都需要重新整理。

    然後我們考慮在什麼情況下可以減少重新整理的次數？如果存在多個相同的字元，那麼我們就可以隻刷一遍了，形式化以後，我們隻考慮第i個字元與第k個字元是否相等，因為這種判斷必定會蔓延到整個區間，當str2[i]==str2[k]，那麼我們有兩種政策，要麼把[i+1,k-1]這個區間刷完，然後分别刷i和k；要麼首先刷k，并且刷k的時候順便把i也刷了，然後再刷[i+1,k-1]。很明顯第二種方案要好，是以dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])。

    上面求解完成之後并沒有完成，因為我們是假設str1為空串得到的最優解，事實上如果str1[i]==str2[i]，那麼i這個位置是不用刷的。我們首先讓res[i]=dp[0][i]，假設res中存放的就是最優解，那麼當str1[[i]==str2[i]的時候，res[i]=res[i-1]（如果i==0，res[i]=0）；否則我們就需要找出一個最優解，由于我們已經知道了[0,i-1]的最優解，是以res[i]的最優解可以由res[k]和dp[k+1][i]得出，至于是哪一個k，我們就需要周遊一下。

/***********************
功能：給出兩個字元串，将一個轉換成另一個，方法是将一段區間設定為同一個字元，問最少次數
參數：兩個字元串
傳回值：最少重新整理次數
***********************/

#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 110
using namespace std;


char str1[maxn],str2[maxn];
int dp[maxn][maxn];

void get_dp(int n)
{
    int i,j,k,len;
    memset(dp,0,sizeof(dp));
    for(len=1;len<=n;len++)
    {
        for(i=0;i<=n-len;i++)
        {
            j=i+len-1;
            dp[i][j]=dp[i+1][j]+1;
            for(k=i+1;k<=j;k++)
            {
                if(str2[i]==str2[k])
                    dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
            }
        }
    }

}

int solve(int n)
{
    get_dp(n);
    int res[maxn];
    int i,j;
    for(i=0;i<n;i++)
        res[i]=dp[0][i];
    for(i=0;i<n;i++)
    {
        if(str1[i]==str2[i])
        {
            if(i==0)
                res[i]=0;
            res[i]=res[i-1];
        }
        else
        {
            for(j=0;j<=i-1;j++)
                res[i]=min(res[i],res[j]+dp[j+1][i]);
        }
    }
    return res[n-1];

}

int main()
{
    int len;
    while(~scanf("%s%s",str1,str2))
    {
        len=strlen(str1);
        printf("%d\n",solve(len));
    }
    return 0;
}