【2014广州市选day1】JZOJ2020年9月12日提高B组T4 字符串距离

题目

Description

给出两个由小写字母组成的字符串 X 和Y ，我们需要算出两个字符串的距离，定义如下：
1)我们可以在字符串的头、尾、中间插入若干空格，组成一个新的扩展串
2)对X扩展成扩展串X1，对Y扩展成扩展串Y1，并且令X1和Y1具有相同的长度
3)定义X1、Y1的距离为每个对应的字符的距离之和，其中两个空格的距离为0，两个非空格字符的距离为其ASCII码之差的绝对值，一个空格字符到任意非空格字符的距离为K
4)对于字符串X、Y，必然存在两个等长的扩展串X1、Y1，使得X1、Y1的距离达到最少，我们将这一距离定义为字符串X、Y的距离

Input

输入为三行，前两行是30位以内的由小写字母组成的字符串，第三行是整数K（0<=K<=30）

Output

输出一行为一个整数，代表两个字符串的距离

Sample Input

cmo
snmn
2

Sample Output

题解

题意

给出两个字符串和字符串距离的定义
求这两个字符串的最短距离

分析

考虑(DP)
设(f[i][j])为第一个字符串到了第(i)个位置，第二个字符串到了第(j)个位置
初始化：
(f[i][0]=i*k,f[0][i]=k*i)
那么就有
(f[i][j]=minegin{cases}f[i-1][j-1]+abs(a[i]-b[j])\f[i-1][j]+k\f[i][j-1]+kend{cases})

Code

#include<bits/stdc++.h>
using namespace std;
int l1,l2,k,a[35],c[35],f[35][35];
char ch;
int main()
{
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	ch=getchar();
	while (ch<'a'||ch>'z') ch=getchar();
	while (ch>='a'&&ch<='z')
	{
		a[++l1]=ch-'a'+1;
		ch=getchar();
	}
	while (ch<'a'||ch>'z') ch=getchar();
	while (ch>='a'&&ch<='z')
	{
		c[++l2]=ch-'a'+1;
		ch=getchar();
	}
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9')
	{
		k=(k<<1)+(k<<3)+(ch-'0');
		ch=getchar();
	}
	for (int i=1;i<=l1;++i)
		f[i][0]=k*i;
	for (int i=1;i<=l2;++i)
		f[0][i]=k*i;
	for (int i=1;i<=l1;++i)
		for (int j=1;j<=l2;++j)
			f[i][j]=min(f[i-1][j-1]+abs(a[i]-c[j]),min(f[i-1][j],f[i][j-1])+k);
	printf("%d
",f[l1][l2]);
	fclose(stdin);fclose(stdout);
	return 0;
}