网站做app开发,wordpress淘宝客模板,网页版梦幻西游手游,网站上的验证码怎么做题目
大概#xff08;又大概#xff1f;#xff09;就是输入t组数据#xff0c;每组数据输入两个字符串#xff08;又是两个字符串#xff1f;#xff09; 然后我们可以进行以下操作 1.修改一个字符#xff08;如把“a”替换为“b”#xff09; 2.删除一个字符又大概就是输入t组数据每组数据输入两个字符串又是两个字符串 然后我们可以进行以下操作 1.修改一个字符如把“a”替换为“b” 2.删除一个字符如把“traveling”变为“travelng” 然后我们求出让第一个字符串和第二个字符串相同最少需要几步操作。 输入
3 abcdefg abcdef ab ab mnklj jlknm
输出
1 0 4 解题思路
其实我之前做过一道题叫做编辑距离 网址这里是网址 跟这题差不多用f[i][j]表示从a[i]到b[i]的最短编辑距离。 这里列出动态转移方程 f[i][j]min(f[i-1][j-1]1,f[i-1][j]1,f[i][j-1]1) f[i-1][j-1]1 表示改变该字符 f[i-1][j]1 表示删去A串一个字符 f[i][j-1]1 表示删去B串一个字符 贴代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int f[1002][1002],n,m,w;
char s1[1002],s2[1002];
int main()
{scanf(%d,w);for (int w11;w1w;w1){memset(f,0,sizeof(f));//清空scanf(%s%s,s1,s2);mstrlen(s1);nstrlen(s2);for (int i1;im;i) f[i][0]i;//将s1的1-i变为空串就是删去i个字符//编辑距离为ifor (int i1;in;i) f[0][i]i;//同上for (int i1;im;i)for (int j1;jn;j)if (s1[i-1]s2[j-1]) f[i][j]f[i-1][j-1];//如果两个字符一样就不需编辑 else {f[i][j]min(min(f[i-1][j-1]1,f[i-1][j]1),f[i][j-1]1);//求三种情况的最小值}printf(%d\n,f[m][n]);}return 0;
}
