P8703 [蓝桥杯 2019 国 B] 最优包含 题解

· · 题解

P8703 [蓝桥杯 2019 国 B] 最优包含 题解

题目链接

分析

对于这类的字符串问题，可以考虑动规。

不妨设 dp_{i,j} 为修改 s 的前 i 个字符、使得 s 的前 i 个字符能够包含 t 的前 j 个字符的最少次数。

此时需要分类讨论 s_i 与 t_j 是否相等的情况。

  1. 若 s_i=t_j：则不用修改，可以直接 dp_{i,j}\leftarrow dp_{i-1,j-1}。（“\leftarrow”为赋值的意思，相当于代码中的 =）

  2. 若 s_i\ne t_j：t_j 要么在 s 中已经出现过（dp_{i,j}\leftarrow dp_{i-1,j}）；要么在 s 中没出现过，要修改 s_i（dp_{i,j}\leftarrow dp_{i-1,j-1}+1）。

注意：dp 数组的在初始的时候需要使 dp_{i,0} (0\le i\le|s|) 为 0，使 dp_{i,j} (0\le i\le|s|,1\le j\le |t|) 为 +\infty，dp_{i,j} 的定义可以解释这一点。

AC 代码

#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define maxn 1010
int dp[maxn][maxn];    //dp[i][j]:修改s的前i个字符、使得s的前i个字符能够包含t的前j个字符的最少次数
string s,t;

int main(){
    cin>>s>>t;
    s = " "+s;t = " "+t;
    memset(dp,inf,sizeof dp);
    for(int i=0;i<=s.size();i++) dp[i][0] = 0;
    for(int i=1;i<=s.size();i++) for(int j=1;j<=s.size();j++){
        if(s[i]==t[j]) dp[i][j] = dp[i-1][j-1];
        else dp[i][j] = min(dp[i-1][j-1]+1,dp[i-1][j]);
    }
    printf("%d",dp[s.size()][t.size()]);
    return 0;
}