【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

7

题解

题意

给出两个字符串和字符串距离的定义

求这两个字符串的最短距离

分析

考虑\(DP\)

设\(f[i][j]\)为第一个字符串到了第\(i\)个位置，第二个字符串到了第\(j\)个位置

初始化：

\(f[i][0]=i*k,f[0][i]=k*i\)

那么就有

\(f[i][j]=min\begin{cases}f[i-1][j-1]+abs(a[i]-b[j])\\f[i-1][j]+k\\f[i][j-1]+k\end{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\n",f[l1][l2]);

	fclose(stdin);fclose(stdout);

	return 0;

}