Massive Algorithms: hdu 2476

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

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

https://blog.csdn.net/wiking__acm/article/details/8362562
首先突破的是，想出这道题是区间的动态规划。
区间的动态规划，可以按区间长度循环，从小到大
然后想出，每次刷的区间，肯定不是相交的关系，要么包含，要么相离
接着看出，对每个区间，首尾字母（在目标串中的）一定是相同的，否则这个区间包含最后那个字母是没有意义的
但是，接下来问题就来了，因为每次刷了一个区间后，在求这个被刷区间内的小区间时，原来的dp值已经无效了
因为这时不是从初始串变到目标串，而是从被刷后的串变到目标串。
这样难道要再加一维状态记录当前串是哪些字母吗？可是这样感觉做不下去了
这里实在想不下去了，搜了解题报告后发现一种思路：
先不管初始串，把题目改为按照原来的规则，直接构造一个目标串，问最少需要几步？
这样，之前卡住的不断变化的串就不用考虑了，因为我不考虑当前串是什么，只考虑哪一部分已经匹配目标串
于是，用dp[i][j]记录从把i~j区间的空串变化到目标串，
初始化方程：dp[i][j] = dp[i+1][j] + (t[i]==t[j]?0:1);
//0的意思是，i不用考虑了，因为可以在刷j时“顺便”把它刷了，注意
//if(t[i] == t[j]) dp[i][j] = dp[i+1][j-1]+1是不对的，这样答案是偏大的
变化方程：if(t[i] == t[k]) dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
这样有了dp值后，再来求这个题目的ans,ans[i]代表0~i初始串变到目标串所需的最少步数
对ans[i],枚举出所有的情况即可

int dp[105][105];
int ans[105];
int main(){
char s[105],t[105];

while(scanf("%s%s",s,t) != EOF){
int n = strlen(s);
for(int k = 1;k <= n;k++){
for(int i = 0;i < n-k+1;i++){
if(k == 1) dp[i][i+k-1] = 1;
else dp[i][i+k-1] = dp[i+1][i+k-1] + (t[i]==t[i+k-1]?0:1);
for(int j = i+1;j < i+k-1;j++){
if(t[i] == t[j])
dp[i][i+k-1] = min(dp[i][i+k-1],dp[i+1][j]+dp[j+1][i+k-1]);
}
}
}
for(int i = 0;i < n;i++){
ans[i] = dp[0][i];
if(s[i] == t[i]) ans[i] = ans[i-1];
for(int j = 0;j < i;j++){
ans[i] = min(ans[i],ans[j]+dp[j+1][i]);
}
}
cout << ans[n-1] << endl;
}
return 0;
}

http://www.voidcn.com/article/p-vrrlyuoa-bmr.html

题意：两个字符串，操作：选取一段变为相同的字符，求有a串变为b串最小的操作次数

先考虑从空串变为b串需要的最少操作次数

dp[i] [j]表示i到j段变成b串需要的最少操作次数

dp[i] [j] = min( dp[i+1] [k] + dp[k+1] [j])（其中k满足b[k]==b[i]）因为对于i+1到k段，无论要求把串变成什么样，我始终可以第一次把他全变为b【k】边界这个字符，这样就可以把b[i]也改变。（区间dp实现）

在考虑将a串变为b串的最小操作次数，当a[i]==b[i]时这个点是不需要在改的(ans[i]=ans[i-1])，而前面也可能存在这种不需要改的点

所以ans[i]=min( ans[k] + dp[k+1][i] )(k<i)

    int i,j,k;
    while(cin>>a>>b)
    {
        memset(ans,0,sizeof(ans));
        memset(dp,0,sizeof(dp));
        for(i=0;i<a.size();i++)
        dp[i][i]=1;

        for(i=1;i<a.size();i++)
        {
            for(j=0;j+i<a.size();j++)
            {
                dp[j][j+i]=dp[j+1][j+i]+1;
                for(k=j+1;k<=j+i;k++)
                {
                    if(b[k]==b[j])
                    dp[j][j+i]=min(dp[j][j+i],dp[j+1][k]+(k==j+i?0:dp[k+1][j+i]));
                }
            }
        }
        for(i=0;i<a.size();i++)
        {
            if(a[i]==b[i])
                ans[i]=min(dp[0][i],i?ans[i-1]:0);
            else
                ans[i]=dp[0][i];
            for(j=0;j<i;j++)
                ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
        }
        cout<<ans[a.size()-1]<<endl;
    }

思路是先求出从空白串转化到b串要花多少次

然后比较a串和b串相同元素的个数在优化答案

hdu 2476 - String Printer

Labels

Popular Posts