南邮 OJ 1239 字符串比较问题

字符串比较问题

时间限制(普通/Java) :  1000 MS/ 3000 MS          运行内存限制 : 65536 KByte

总提交 : 57            测试通过 : 9 

比赛描述

对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0；空格与其它字符的距离为一定值k。

在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A 和B 的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。

对于给定的字符串A和B，试设计一个算法，计算其扩展距离。对于给定的字符串A和B，编程计算其扩展距离。

输入

输入的第1行是字符串A；第2行是字符串B。第3行是空格与其它字符的距离定值k。(A,B长度均小于2000）

输出

输出计算出的字符串A和B的扩展距离。

样例输入

cmc

snmn

2

样例输出

10

提示

undefined

题目来源

算法设计与实验题解

//dp[i][j]:a[1……i]和b[1……j]的扩展距离

#include<iostream>
#define MAX_N 2002
char a[MAX_N],b[MAX_N];
short dp[MAX_N][MAX_N];

int main(){
//	freopen("test.txt","r",stdin);
	int k,lenA,lenB,i,j,minVal,temp;
	scanf("%s%s%d",a+1,b+1,&k);
	lenA = (int)strlen(a+1);
	lenB = (int)strlen(b+1);
	dp[0][0] = 0;
	for(i=0;i<=lenA;i++){
		for(j=0;j<=lenB;j++){
			if(i+j){
				minVal = INT_MAX;
				if(i && (temp=dp[i-1][j]+k)<minVal){
					minVal = temp;
				}
				if(j && (temp=dp[i][j-1]+k)<minVal){
					minVal = temp;
				}
				if(i && j && (temp=dp[i-1][j-1]+abs(a[i]-b[j]))<minVal){
					minVal = temp;
				}
				dp[i][j] = minVal;
			}
		}
	}
	printf("%hd\n",dp[lenA][lenB]);
}