题解 P2268 [HNOI2002]DNA分子的最佳比对
ctq1999
·
·
题解
传送门
题意简述
给你两个字符串
让你插入一个空格、更改一个字符、插入一个新的字符来使这两个字符串有最大匹配数
其中若一个下标上完全匹配加1pts，不同加0pts，若两者中有空格，加-2pts
思路
考虑动态规划
第一个字符串用s1来表示，第二个用s2表示
则动态转移方程：
```c++
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$个字符与空格比较
预处理：
```c++
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`
## 代码
```c++
#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;
}
```
> 日拱一卒，功不唐捐