首页 > ACM题库 > HDU-杭电 > HDU 3831-DICS-动态规划-[解题报告]HOJ
2015
04-13

HDU 3831-DICS-动态规划-[解题报告]HOJ

DICS

问题描述 :

I think all of you must be skilled in the classic problem Levenshtein Distance , which is more commonly known as Edit Distance. For more historic knowledge and basic concepts, see http://en.wikipedia.org/wiki/Levenshtein_distance .
This time, we are involved in a more complicated one: given two strings SOURCE and DESTINATION , we have 4 operations
Delete: remove the ith character.
Insert: in pos i(the ith character in the first string),you can insert a character, any one as you like.
Change: in pos i,you can change that original character to any other character(of course you won’t change it to itself).
Suffix change: which means you can change all characters to an identical character, from the ith pos to the end. For instance: abcdefg, you can make this operation in character b,maybe you can use d and the result is adddddd, or if you use e the result is aeeeeee or if you use this operation in character c with character f,the result is abfffff.
With the help of Suffix change, sometimes the edit distance can be greatly shortened. See the following example

abcdefg
ccccccg

You can first replace every character from the beginning to the end with c,and the first string will be ccccccc,then change the last character c to g. In such way,we can see the edit distance is 2.

输入:

Input consists of several test cases, each case contains two line,the first line will show you the SOURCE string, the second line provide the DESTINATION string. You should write a program to caculate the minimum number of operations(delete, insert, changes, suffix change as I mentioned before) of transforming the SOURCE to DESTINATION. You can assume none of string in any case will be longer than "500". Input ends with a line consists of a ‘#’.
PAY ATTENTION:Both strings consist of either lower or upper letters,in other word in each position there is 52 possibilities.There will be at most 15 test cases.

输出:

Input consists of several test cases, each case contains two line,the first line will show you the SOURCE string, the second line provide the DESTINATION string. You should write a program to caculate the minimum number of operations(delete, insert, changes, suffix change as I mentioned before) of transforming the SOURCE to DESTINATION. You can assume none of string in any case will be longer than "500". Input ends with a line consists of a ‘#’.
PAY ATTENTION:Both strings consist of either lower or upper letters,in other word in each position there is 52 possibilities.There will be at most 15 test cases.

样例输入:

abcdefg
aaaaaaa
#

样例输出:

1

题意:

给定2个字符串,对上面的字符串进行修改使得其变成下面的字符串

有4种操作:

1、删除一个字符

2、插入一个字符

3、修改一个字符

4、把任意位置开始 [i, strlen] 修改为相同的字符

问最少需要几次操作

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
#define mod 1000000007
#define inf 0x7f7f7f7f
#define N 505
int dp[N][N][55];//dp[i][j][k] 表示前i个字符与前j个字符匹配 最后一次使用后缀修改为字符k的状态需要最小的次数
//52表示没有使用过后缀修改
//dp[i][j][k] 可以从删除 dp[i-1][j][k]+1
//dp[i][j][k] 从插入	 dp[i][j-1][k]+1
//dp[i][j][k] 替换       dp[i-1][j-1][k]+1
//dp[i][j][k] 修改后缀	 dp[i-1][j-1][any]+1 if(k==p[j]) dp[i][j][k]=min(dp[i-1][j-1][k]);
char s[N],p[N];
int  a[N],b[N];
int la, lb;
//把s->p最少需要修改s几步
int main()
{
	int i, j, k, u, v;
	while(scanf("%s",s+1),s[1]!='#'){
		scanf("%s",p+1);
		for(i=1;s[i];i++)if(islower(s[i]))a[i] = s[i]-'a';else a[i] = s[i]-'A'+26;
		for(i=1;p[i];i++)if(islower(p[i]))b[i] = p[i]-'a';else b[i] = p[i]-'A'+26;
		memset(dp, inf, sizeof dp);
		la = strlen(s+1), lb = strlen(p+1);

		dp[0][0][52] = 0;
		for(i = 1; i <= la; i++)dp[0][i][52]=dp[i][0][52] = i;
		for(i = 1; i <= la; i++)
		{
			for(j = 1; j <= lb; j++)
			{
				for(k = 0; k < 52; k++)
				{
					u = inf;
					if(b[j]==k)
						u = dp[i-1][j-1][k];
					else 
					{
					u = min(u, dp[i-1][j][k]+1);
					u = min(u, dp[i][j-1][k]+1);
					u = min(u, dp[i-1][j-1][k] +1);
					dp[i][j][b[j]] = min(dp[i][j][b[j]],dp[i-1][j-1][k]+1);
					}
					dp[i][j][k] = min(u, dp[i][j][k]);
				}
				u = inf;
				if(a[i]==b[j])
					u = dp[i-1][j-1][52];
				else {
					u = min(u, dp[i-1][j][52]+1);
					u = min(u, dp[i][j-1][52]+1);
					u = min(u, dp[i-1][j-1][52] +1);
					dp[i][j][b[j]] = min(dp[i][j][b[j]], dp[i-1][j-1][52]+1);
				}
				dp[i][j][52] = min(dp[i][j][52], u);
			}
		}

		int ans = 1000000000;
		for(i = 0; i <= 52; i++)ans = min(ans, dp[la][lb][i]);
		printf("%d\n",ans);	
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acmmmm/article/details/24272537


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. [email protected]

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。