当前位置: 代码迷 >> 综合 >> caioj 1070 动态规划入门(二维一边推3:字符距离)(最长公共子序列拓展)
  详细解决方案

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

热度:42   发布时间:2023-09-20 19:54:26.0

复制上一题总结

caioj 1069到1071 都是最长公共字序列的拓展,我总结出了一个模型,屡试不爽
   (1) 字符串下标从1开始,因为0用来表示字符为空的情况,而不是第一个字符 
   (2)初始化问题。
         一般设f[i][j]为第一个字符前i个,第二个字符前j个的最优价值
         f[0][0] = 0
          然后要初始化f[i][0], f[0][i]

      这个时候要根据题意。
         这个时候就是一个字符有,一个字符空的情况
   (3)然后就可以两层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;
}

 

  相关解决方案