做美妆的网站,安徽省建设厅,电子商务毕业设计网站建设,北京app开发定制公司题目描述 设有字符串X#xff0c;我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串#xff0c;如字符串X为”abcbcd”#xff0c;则字符串“abcb□cd”#xff0c;“□a□bcbcd□”和“abcb□cd□”都是X的扩展串#xff0c;这里“□”代表空格字符。 如…题目描述 设有字符串X我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串如字符串X为”abcbcd”则字符串“abcb□cd”“□a□bcbcd□”和“abcb□cd□”都是X的扩展串这里“□”代表空格字符。 如果A1是字符串A的扩展串B1是字符串B的扩展串A1与B1具有相同的长度那么我扪定义字符串A1与B1的距离为相应位置上的字符的距离总和而两个非空格字符的距离定义为它们的ASCII码的差的绝对值而空格字符与其他任意字符之间的距离为已知的定值K空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中必定存在两个等长的扩展串A1、B1使得A1与B1之间的距离达到最小我们将这一距离定义为字符串A、B的距离。 请你写一个程序求出字符串A、B的距离。 输入输出格式 输入格式 输入文件第一行为字符串A第二行为字符串B。A、B均由小写字母组成且长度均不超过2000。第三行为一个整数K1≤K≤100表示空格与其他字符的距离。 输出格式 输出文件仅一行包含一个整数表示所求得字符串A、B的距离。 思考这道题是两个字符串之间的动态规划对于每一个相对应的位置都会有三种情况字母对空格空格对字母字母对字母而且三种情况的计算方法都已经了解所以我们可以采取直接设法我们定义f[i][j]代表匹配到字符串S1的第i位和S2的第j位时能达成的最优解所以综合以上三种计算情况我们可以推出状态转移方程 f[i][j]min(f[i-1][j-1]abs(s1[i]-s2[j]),min(f[i-1][j]k,f[i][j-1]k)); 这样这道题就再也没什么难点了 下面上代码 1 #includeiostream2 #includecstdio3 #includecstdlib4 #includecstring5 #includecmath6 #includestring7 #includealgorithm8 #includequeue9 using namespace std;
10 const int MAXN2002;
11 int f[MAXN][MAXN];
12 char s1[MAXN],s2[MAXN];
13 int n,m,k,len1,len2;
14 int main()
15 {
16 scanf(%s%s,s11,s21);cink;
17 len1strlen(s11);len2strlen(s21);
18 for(int i1;ilen1;i) f[i][0]kf[i-1][0];
19 for(int i1;ilen2;i) f[0][i]kf[0][i-1];
20 for(int i1;ilen1;i){
21 for(int j1;jlen2;j){
22 f[i][j]min(f[i-1][j-1]abs((int)s1[i]-(int)s2[j]),min(f[i-1][j]k,f[i][j-1]k));
23 }
24 }
25 coutf[len1][len2]endl;
26 return 0;
27 } 动态规划 转载于:https://www.cnblogs.com/Alan-Luo/articles/9184548.html
