蓝桥杯2019年第十届国赛真题-最优包含

题目

题目链接

题解

动态规划。

（有点像最长公共子序列）

状态定义：dp[i][j]表示S前i个字符要想包含T前j个字符，需要经过的最少修改次数。

转移方程： ① S[i] == T[j]：此时无需进行变换，S前i个字符要想包含T前j个字符需要经过的最少修改次数就等于S前i-1个字符要想包含T前j-1个字符需要经过的最少修改次数，即dp[i][j] = dp[i-1][j-1] ② S[i] != T[j]：两种情况转移而来。其一，为了让S前i个字符包含T前j个字符，我们只需要让让S前i-1个字符包含T前j-1个字符，同时将S[i]修改成T[j]，即dp[i][j] = dp[i-1][j-1] + 1；其二，S前i-1个字符包含T前j个字符的修改次数更少的话，我们也可以不修改S[i]而是直接在第i个字符之前就已经包含T前j个字符了，即dp[i][j] = dp[i-1][j]

初始化：用S的前任意个字符都可以包含T的前0个字符，修改个数为0，所以dp[i][0] = 0。

自己写的时候写（蒙）的代码就比标准答案在不相等的情况下，多了个对dp[i][j-1]取min，其他完全一样，但还是错了，而且是蒙的。

代码

#include
using namespace std;
const int N = 1e3+10;
string s, t;
int f[N][N];
int main()
{
	cin >> s >> t;
	int n = s.size(), m = t.size();
	s = '.' + s, t = '.' + t;
	
	memset (f, 0x3f, sizeof f);
	for (int i = 0;i