洛谷 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的长度]里。 

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define int long long
 7 #define maxn 2000+10
 8 using namespace std;
 9 inline int read()
10 {
11     int x=0;
12     bool f=1;
13     char c=getchar();
14     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
15     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
16     if(f) return x;
17     return 0-x;
18 }
19 inline void write(int x)
20 {
21     if(x<0){putchar('-');x=-x;}
22     if(x>9)write(x/10);
23     putchar(x%10+'0');
24 }
25 char a[maxn],b[maxn];
26 int k,lena=1,lenb=1;
27 int dp[maxn][maxn];
28 inline int min_four(int x,int y,int z,int o)
29 {
30     return min(min(x,y),min(z,o));
31 }
32 inline int fig(char x,char y)
33 {
34     int nx=x-'0',ny=y-'0';
35     return abs(nx-ny);
36 }
37 signed main()
38 {
39     memset(dp,127,sizeof(dp));
40     while(1)
41     {
42         int in=getchar();
43         if(in=='\n')
44         {
45             lena--;
46             break;
47         }
48         a[lena]=in;
49         lena++;
50     }
51     while(1)
52     {
53         int in=getchar();
54         if(in=='\n')
55         {
56             lenb--;
57             break;
58         }
59         b[lenb]=in;
60         lenb++;
61     }
62     k=read();
63     dp[0][0]=0;
64     for(int i=1;i<=lena;i++) dp[i][0]=dp[i-1][0]+k;
65     for(int i=1;i<=lenb;i++) dp[0][i]=dp[0][i-1]+k;
66     for(int i=1;i<=lena;i++)
67         for(int j=1;j<=lenb;j++)
68         {
69             dp[i][j]=min_four(dp[i][j],dp[i-1][j]+k,dp[i][j-1]+k,dp[i-1][j-1]+fig(a[i],b[j]));
70         }
71     write(dp[lena][lenb]);
72     return 0;
73 } 

请各位大佬斧正