RQNOJ 514 字串距离：dp & 字符串

题目链接：https://www.rqnoj.cn/problem/514

题意：

　　设有字符串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 = "ABC", B = "DEFG"

　　这是其中的一种匹配情况。

　　而每一种匹配，无非是由一些上下字符对组合而成。

　　比如例子的组成：(A,_) , (_,D) , (_,E) , (B,F) , (_,G) , (C,_)

　　有两个很显然的结论：

　　　　（1）一种匹配不可能有一组为(_,_)，因为它对答案不能做出任何贡献。

　　　　（2）字符组的排列有顺序，不可能存在左边为(A,E)，右边为(B,D)。

　　那么可以转化问题：

　　　　求一个这样的匹配，上面只有A串字符，下面只有B串字符，同时使得匹配中的每一个字母与两个原串中的字母一一对应。

　　类似背包吧。。。

　　表示状态：

　　　　dp[i][j] = min distance

　　　　i：A串考虑到第i个字符

　　　　j：B串考虑到第j个字符

　　找出答案：

　　　　ans = dp[a.len][b.len]

　　如何转移：

　　　　now: dp[i][j]

　　　　三种决策，往匹配中添加字符对：

　　　　　　（1）(a[i],_)

　　　　　　（2）(_,b[j])

　　　　　　（3）(a[i],b[j])

　　　　分别对应方程：

　　　　　　dp[i+1][j] = min dp[i][j] + space

　　　　　　dp[i][j+1] = min dp[i][j] + space

　　　　　　dp[i+1][j+1] = min dp[i][j] + abs(a[i]-b[j])

　　边界条件:

　　　　dp[0][0] = 0

　　　　others = -1

　　　　什么都还没有添加。。。

AC Code:

 // state expression:

 // dp[i][j] = min distance

 // i: considering ith char in str a

 // j: considering ith char in str b

 //

 // find the answer:

 // ans = dp[a.len][b.len]

 //

 // transferring:

 // now: dp[i][j]

 // dp[i+1][j] = min dp[i][j] + space

 // dp[i][j+1] = min dp[i][j] + space

 // dp[i+1][j+1] = min dp[i][j] + abs(a[i]-b[j])

 //

 // boundary:

 // dp[0][0] = 0

 // others = -1

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #define MAX_L 2005

 using namespace std;

 int space;

 int dp[MAX_L][MAX_L];

 string a,b;

 void read()

 {

     cin>>a>>b>>space;

 }

 int my_min(int a,int b)

 {

     if(a==-) return b;

     if(b==-) return a;

     return min(a,b);

 }

 void solve()

 {

     memset(dp,-,sizeof(dp));

     dp[][]=;

     for(int i=;i<=a.size();i++)

     {

         for(int j=;j<=b.size();j++)

         {

             if(dp[i][j]!=-)

             {

                 dp[i+][j]=my_min(dp[i+][j],dp[i][j]+space);

                 dp[i][j+]=my_min(dp[i][j+],dp[i][j]+space);

                 dp[i+][j+]=my_min(dp[i+][j+],dp[i][j]+abs(a[i]-b[j]));

             }

         }

     }

 }

 void print()

 {

     cout<<dp[a.size()][b.size()]<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

RQNOJ 514 字串距离：dp & 字符串

最新文章

热门文章