字符串的距离(dp (star ))
- 时限:(1s) 内存:(256M)
Descrption
- 设有字符串 (X),我们称在 (X) 的头尾及中间插入任意多个空格后构成的新字符串为 (X) 的扩展串,如字符串 (X)为“(abcbcd)”,则字符串“(abcb□cd)”,“(□a□bcbcd□)” 和 “(abcb□cd□)” 都是 (X) 的扩展串,这里“ (□) ”代表空格字符。
- 如果 (A_1) 是字符串 (A) 的扩展串,(B_1) 是字符串 (B) 的扩展串,(A_1) 与 (B_1) 具有相同的长度,那么我们定义字符串 (A_1) 与 (B_1) 的距离为相应位置上的字符的距离总和:
- 两个非空格字符的距离定义为它们的 (ASCII) 码的差的绝对值
- 空格字符与其它任意字符之间的距离为已知的定值 (K),
- 空格字符与空格字符的距离为 (0)。
- 在字符串 (A,B) 的所有扩展串中,必定存在两个等长的扩展串 (A_1,B_1),使得 (A_1) 与 (B_1) 之间的距离达到最小,我们将这一距离定义为字符串 (A,B) 的距离。
- 请你写一个程序,求出字符串 (A,B) 的距离
Input
- 输入文件第一行为字符串 (A) 。
- 第二行为字符串 (B),(A,B) 均由小写字母组成且长度均不超过 (2000) 。
- 第三行为一个整数 (K,1≤K≤100) ,表示空格与其它字符的距离。
Output
- 输出文件仅一行包含一个整数,表示要求的字符串 (A,B) 的距离。
Sample Input
cmc
snmn
2
Sample Output
10
Hint
- 来源:(luogup1279)
分析
- 这个 (dp) 应该还是比较好想的,类似的模型我们可以参照最大公共子序列,定义状态 (dp[i][j]) :表示第一个字符串处理到第 (i),第二个字符串处理到第 (j) 个的最小距离。
- 转移方程:(dp[i][j]=min(dp[i-1][j-1]+abs(s1[i]-s2[j]),min(dp[i-1][j]+k,dp[i][j-1]+k)))
- (dp[i-1][j-1]+abs(s1[i]-s2[j])) :表示 (s1[i]) 和 (s2[j]) 对齐。
- (dp[i-1][j]+k) :表示 (s1[i]) 与空格对齐。
- (dp[i][j-1]+k) :表示 (s2[i]) 与空格对齐。
- 临界条件初始化:
- (dp[i][0]=i*k, dp[0][i]=i*k) :均和空格对位。
- 求最小值,其他情况初始化为一个大数。
Code
#include <bits/stdc++.h>
const int maxn=2000+5;
char s1[maxn],s2[maxn];
int dp[maxn][maxn],len1,len2,k;
void Init(){
scanf("%s%s",s1,s2);
scanf("%d",&k);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;len1=strlen(s1);len2=strlen(s2);
for(int i=1;i<=len1;++i)
dp[i][0]=i*k;
for(int i=1;i<=len2;++i)
dp[0][i]=i*k;
}
void Solve(){
for(int i=1;i<=len1;++i)
for(int j=1;j<=len2;++j){
dp[i][j]=std::min(dp[i-1][j]+k,dp[i][j-1]+k);
dp[i][j]=std::min(dp[i][j],dp[i-1][j-1]+abs(s1[i-1]-s2[j-1]));
}
printf("%d
",dp[len1][len2]);
}
int main(){
Init();
Solve();
return 0;
}