P1279 字串距离【洛谷算法习题】
P1279 字串距离
网页链接
P1279 字串距离
题目描述
设有字符串X XX，我们称在X XX的头尾及中间插入任意多个空格后构成的新字符串为X XX的扩展串，如字符串X XX为abcbcd \verb!abcbcd!abcbcd，则字符串abcb␣cd \verb!abcb␣cd!abcb␣cd，␣a␣bcbcd␣ \verb!␣a␣bcbcd␣!␣a␣bcbcd␣和abcb␣cd␣ \verb!abcb␣cd␣!abcb␣cd␣都是X XX的扩展串，这里␣ \verb!␣!␣代表空格字符。
如果A 1 A_1A1是字符串A AA的扩展串，B 1 B_1B1是字符串B BB的扩展串，A 1 A_1A1与B 1 B_1B1具有相同的长度，那么我们定义字符串A 1 A_1A1与B 1 B_1B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0 00。在字符串A AA、B BB的所有扩展串中，必定存在两个等长的扩展串A 1 A_1A1，B 1 B_1B1，使得A 1 A_1A1与B 1 B_1B1之间的距离达到最小，我们将这一距离定义为字符串A AA，B BB的距离。
请你写一个程序，求出字符串A AA，B BB的距离。
输入格式
输入文件第一行为字符串A AA，第二行为字符串B BB。A AA，B BB均由小写字母组成且长度均不超过2000 20002000。第三行为一个整数K ( 1 ≤ K ≤ 100 ) K(1\leq K\leq 100)K(1≤K≤100)，表示空格与其他字符的距离。
输出格式
输出文件仅一行包含一个整数，表示所求得字符串A , B A,BA,B的距离。
输入输出样例 #1
输入 #1
cmc snmn 2输出 #1
10解题思路
本题核心是动态规划（DP），本质是变形的编辑距离问题，求解两字符串扩展后的最小匹配距离。定义dp[i][j]为字符串A前i个字符、字符串B前j个字符匹配后的最小距离。状态转移有三种情况：A第i字符匹配B第j字符，累加ASCII差绝对值；A第i字符匹配空格，加定值K；B第j字符匹配空格，加定值K。初始化边界：dp[i][0]、dp[0][j]分别为全空格匹配的代价。算法时间复杂度O ( l e n ( A ) × l e n ( B ) ) O(len(A)×len(B))O(len(A)×len(B))，完美适配字符串长度≤2000的数据范围。
总结
核心逻辑：动态规划模拟字符与空格的三种匹配方式，取最小代价。
关键操作：定义DP状态、三种转移方程、边界初始化。
效率保障：二维DP线性遍历，400万次运算高效通过，无超时风险。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s1,s2;ll k;cin>>s1>>s2>>k;ll l1=s1.size(),l2=s2.size();vector<ll>a(l1+1),b(l2+1);for(ll i=0;i<l1;i++)a[i+1]=s1[i];for(ll i=0;i<l2;i++)b[i+1]=s2[i];vector<vector<ll>>f(l1+1,vector<ll>(l2+1,INF));for(ll i=1;i<=l1;i++)f[i][0]=i*k;for(ll i=1;i<=l2;i++)f[0][i]=i*k;f[0][0]=0;for(ll i=1;i<=l1;i++){for(ll j=1;j<=l2;j++){f[i][j]=min(f[i][j],f[i][j-1]+k);f[i][j]=min(f[i][j],f[i-1][j]+k);f[i][j]=min(f[i][j],f[i-1][j-1]+abs(a[i]-b[j]));}}cout<<f[l1][l2]<<endl;return0;}