caioj 1070 动态规划入门（二维一边推3：字符距离）（最长公共子序列拓展）

时间：2022-01-11 19:11:16

复制上一题总结

caioj 1069到1071 都是最长公共字序列的拓展，我总结出了一个模型，屡试不爽

   （１） 字符串下标从1开始，因为０用来表示字符为空的情况，而不是第一个字符 

   （２）初始化问题。
        　一般设f[i][j]为第一个字符前ｉ个，第二个字符前ｊ个的最优价值

        　f[0][0] = 0

          然后要初始化f[i][0], f[0][i]

    　　这个时候要根据题意。

        　这个时候就是一个字符有，一个字符空的情况

   （３）然后就可以两层for了
          这个时候记住根据题目有不同的决策，取最优

          一般有匹配字符和不匹配字符（如加空格）两种情况

          按照题目而定  

          最后要注意如果是取min初值要最大，max初值最小

          或者直接用其中一个决策作为初值

依然是套模型

这道题，f[i][0]和f[0][i]就是全是空格，那么就要设为k * i

决策就是匹配字符和加空格，取最优

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 2123;

char a[MAXN], b[MAXN];

int f[MAXN][MAXN], k;

int main()

{

	scanf("%s", a + 1);

	int lena = strlen(a + 1);

	scanf("%s", b + 1);

	int lenb = strlen(b + 1);

	scanf("%d", &k);

	REP(i, 1, lena + 1) f[i][0] = k * i;

	REP(i, 1, lenb + 1) f[0][i] = k * i;

	f[0][0] = 0;

	REP(i, 1, lena + 1)

		REP(j, 1, lenb + 1)

		{

			f[i][j] = f[i-1][j-1] + abs(a[i] - b[j]);

			f[i][j] = min(f[i][j], min(f[i][j-1], f[i-1][j]) + k);

		}

	printf("%d\n", f[lena][lenb]);

	return 0;

}

相关文章