洛谷 P1279 字串距离 题解

每日一题 day24 打卡

Analysis

字符串+dp

仔细观察发现，对于f[i][j],它的值为以下三个值中的最小者：

1. f[i-1][j]+k //a[i]对应空格
2. f[i][j-1]+k //b[j]对应空格
3. f[i-1][j-1]+abs(a[i-1]-b[j-1])// a[i]对应b[j] 我们就得出了动态转移方程，而最终答案就在f[a的长度][b的长度]里。

除此之外，只需注意初始化即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define int long long

 #define maxn 2000+10

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 char a[maxn],b[maxn];

 int k,lena=,lenb=;

 int dp[maxn][maxn];

 inline int min_four(int x,int y,int z,int o)

 {

     return min(min(x,y),min(z,o));

 }

 inline int fig(char x,char y)

 {

     int nx=x-'',ny=y-'';

     return abs(nx-ny);

 }

 signed main()

 {

     memset(dp,,sizeof(dp));

     while()

     {

         int in=getchar();

         if(in=='\n')

         {

             lena--;

             break;

         }

         a[lena]=in;

         lena++;

     }

     while()

     {

         int in=getchar();

         if(in=='\n')

         {

             lenb--;

             break;

         }

         b[lenb]=in;

         lenb++;

     }

     k=read();

     dp[][]=;

     for(int i=;i<=lena;i++) dp[i][]=dp[i-][]+k;

     for(int i=;i<=lenb;i++) dp[][i]=dp[][i-]+k;

     for(int i=;i<=lena;i++)

         for(int j=;j<=lenb;j++)

         {

             dp[i][j]=min_four(dp[i][j],dp[i-][j]+k,dp[i][j-]+k,dp[i-][j-]+fig(a[i],b[j]));

         }

     write(dp[lena][lenb]);

     return ;

 } 

请各位大佬斧正