自动搬运

查看原文

来自洛谷，原作者为

	Versed_sine AFO☆

搬运于2025-08-24 22:41:36，当前版本为作者最后更新于2023-03-30 09:20:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}