自动搬运

查看原文

来自洛谷，原作者为

	ctq1999 今晚はの月が綺麗ですね

搬运于2025-08-24 21:35:47，当前版本为作者最后更新于2019-11-06 14:51:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

题意简述

给你两个字符串

让你插入一个空格、更改一个字符、插入一个新的字符来使这两个字符串有最大匹配数

其中若一个下标上完全匹配加$1pts$，不同加$0pts$，若两者中有空格，加$-2pts$

思路

考虑动态规划

第一个字符串用$s1$来表示，第二个用$s2$表示

$f[i][j]$表示$s1$前i个字符和$s2$前$j$个字符最大得分

则动态转移方程：

f[i][j] = max(f[i - 1][j - 1] + (s[i - 1] == s[j - 1]), f[i][j - 1] - 2, f[i - 1][j] - 2);

• $f[i - 1][j - 1] + (s[i - 1] == s[j - 1])$ 表示$s1$第$i$个字符与$s2$第$j$个字符比较（因为循环是从$1$开始，所以字符串的下标要减去1）

• $f[i][j - 1]$ 表示$s1$第$i$个字符与空格比较

• $f[i - 1][j]$ 表示$s2$第$j$个字符与空格比较

预处理：

for (int i = 1; i <= s1.length(); i++) {
	f[i][0] = f[i - 1][0] - 2;
}
for (int i = 1; i <= s2.length(); i++) {
	f[0][i] = f[0][i - 1] - 2;
}

即$s1$全部和空格比较，$s2$全部和空格比较

如果懂的话就可以自己写了，否则可能对你的收获不大

还没懂的把上面的代码瞎搞在一起，在自己理解一下，差不多就懂了

注意忽略大小写，否则70pts

代码

#include <bits/stdc++.h>

#define MAXN 1010

using namespace std;

string s1, s2;

int l1, l2;

int f[MAXN][MAXN];

int main() {
	cin >> s1 >> s2;
	l1 = s1.length();
	l2 = s2.length();
	
	//忽略大小写 
	for (int i = 0; i < l1; i++) {
		if (s1[i] < 97) s1[i] += 32;
	}
	for (int i = 0; i < l2; i++) {
		if (s2[i] < 97) s2[i] += 32;
	}
	
	//预处理 
	f[0][0] = 0;
	for (int i = 1; i <= l1; i++) {
		f[i][0] = f[i - 1][0] - 2;
	}
	for (int i = 1; i <= l2; i++) {
		f[0][i] = f[0][i - 1] - 2;
	}
	
	//动态规划 
	for (int i = 1; i <= l1; i++) {
		for (int j = 1; j <= l2; j++) {
			int match = 0;
			if (s1[i - 1] == s2[j - 1]) match = 1;
			f[i][j] = max(f[i - 1][j] - 2, f[i][j - 1] - 2);
			f[i][j] = max(f[i][j], f[i - 1][j - 1] + match);
		}
	}
	
	cout << f[l1][l2] << endl;
	return 0;
}

日拱一卒，功不唐捐