hdoj 2476 String painter

원제:

 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

중국어: 두 문자열 a와 문자열 b를 드립니다. 브러시가 하나 있습니다. 한 번에 한 연속 구간의 문자열을 같은 문자로 칠할 수 있습니다. 최소한 몇 번을 칠하면 문자열 a를 b로 칠할 수 있는지 제한합니다.예를 들어 첫 번째 예시 zzzzzfzzzzzz abcdefedcba는 문자열 zzzzfzzzzz를 abcdefedcba로 칠할 것을 요구한다. 첫 번째 단계는 이렇게 칠할 수 있다.
코드:

#include 
using namespace std;
const int maxn = 100 + 10;


char s1[maxn],s2[maxn];
int dp[maxn][maxn];
int ans[maxn];

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>&s1[1])
    {
        cin>>&s2[1];
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
        int len = strlen(&s1[1]);

        for(int R = 1;R<=len ;R++)
        {
            for(int L = R; L>=1; L--)
            {
                dp[L][R] = dp[L+1][R]+1;
                for(int k = L + 1; k<=R ;k++)
                {
                    if(s2[L] == s2[k])
                        dp[L][R] = min(dp[L][R], dp[L+1][k] + dp[k+1][R]);
                }
            }
        }
        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=1;j<=i;j++)
                    ans[i]=min(ans[i],dp[j+1][i] + ans[j]);
            }
        }
        cout<<ans[len]<<endl;
    }
    return 0;
}

대답:
이 문제는 내가 정교한 구간 dp문제 중 하나로 다른 사람의 코드를 한참 동안 보고 나서야 깨달았다- -|.데이터상 문자열의 길이는 최대 100에 불과하다.이것은 시간의 복잡도를 O(n^3) 이내에 완성해야 한다는 것을 의미한다.주어진 사례에 따라 수동으로 시뮬레이션을 해 보면 구간 dp의 모델을 단순히 이용하여 고려하면 매번 상태 이동을 하는 방법은 구간에 따라 고려하고상태 전환 방정식은 다음과 같다. dp [i] [j] [j] = m i n(dp [i] [j]], d p [i] [x-4 1] + p a i n t(x, y) + d p [y + 1] [j] [i] [j]], d p [i] [i] [j] = min (dp [i] [j], dp[i] [j], dp[i] [j], dp[i] [j]], dp[i] [j], dp[i] [j], dp[[i] [[j]]]], dp[i] [j]]], dp[j] [j]]]]]], [[dpi]]]]], [[dpi]]]]]], [[dpi] [[[)에서 paint(x, y)는 a 문자열을 b 문자열로 칠하는 것을 나타낸다. 여기에 문제가 있다. paint(x, y) 함수는 어떻게 실현됩니까?만약 구간 [x, y]를 문자열 b에 대응하는 문자열로 칠하려면, 이 구간을 어떻게 처리해야만 paint 함수를 가장 잘 만들 수 있습니까?이렇게 다시 원래의 문제로 돌아왔다.그래서 이 문제는 구간적으로 고려하기 어렵다.
빈 문자열을 문자열 b로 칠하는 데 필요한 최소한의 칠 횟수를 고려하고 상태 dp[i][j]를 설정하면 빈 문자열 구간 [i, j]을 문자열 b구간 [i, j]로 칠하는 데 필요한 최소한의 칠 횟수를 나타낸다.
상태 이동 방정식은 초기 dp [i] [j] = dp [i+1] [j] + 1dp[i] [j] = dp[i+1] [j] + 1dp[i] [j] = dp[i+1] [j] +1은 첫 번째 문자를 문자열 b[i]에 대응하는 문자로 단독으로 칠할 수 있음을 나타낸다
만약 문자열 b에 b[i]==b[k]가 있다면 그 중에서 k\8712[i+1, j] dp [i] [i] [j] = m i n(dp [i] [j]], d p [i+ 1] [k] [1] [j]) dp[i] [i] [i] [i] [j]] [i] [j] = = m[j] dp[j] = m(dp[[i] = m[j]]]] = m[j] b[k] 문자와 같으면 구간 [i,k]을 한 번에 b[i] 형식으로 칠할 수 있습니다
여기서 질문이 하나 있습니다. 만약에 b[i]=b[k]b[i]=b[k]b[i]==b[k]시 dp[i+1][k]dp[i+1][k]dp[i+1][k]는 구간 [i,k]을 문자열 b[k]로 칠하는 것을 의미하는데 왜 아래의 이런 형식으로 표현할 수 없습니까?d p [i] [j] = m in (dp [i] [j], d p [i + 1] [k] [k] + 1 + d p [k + 1] = m i n (dp [i] [j] [j] [j] [j], d p [i + 1] [k] [k] + 1] [k] + 1 + 1] [k] [k] [k] [k] [k] + 1] [k] [k] [k] + 1] [k] [k] [k] + 1] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] + [k] [k] [k] [k] [k] [k] [k] [k] [k] [k[k-3] + 1 + d p [k+ 1] [j]) dp[i] [j] = min(dp[i] [j], dp[i+1] [k-1] + 1 + dp[k+1] [j]) dp[i] [j]=min(dp[i] [j], dp[i+1] [k-3]+1+dp[k+1][j])
코드에서 볼 수 있듯이 먼저 오른쪽 구간을 매거한 다음에 왼쪽 구간을 매거한다. 여기서 오른쪽 구간은 고정적이다. 하위 상태를 찾아서 현재 상태를 구성하는 가장 좋은 결과를 찾더라도 가장 오른쪽 문자를 참조 기준으로 한다.첫 번째 상태 이동 방정식이 +1이 되지 않는 이유는 b[i]=b[k]b[i]==b[k]b[i]=b[k]]가 구간 [i,k]를 칠할 때, 즉 첫 번째 k의 문자를 처리할 때 이미 전체 구간을 칠한 후 두 번째 방정식을 dp[i+1][k-1][k-1]+1]+1dp[i+1][k-1][k-3]+1 형식으로 쓸 수 없기 때문이다. 왜냐하면 이 형식은 첫 번째 문자와 kk의 문자만 고려하고 칠하는 것이기 때문이다.구간을 표시하지 않았다.