“将A串变为B串”类动态规划题（已修改解释）
今天考试感觉要被虐爆了
就我的感觉来说，后两题绝对是省队水平 Orz Owen第四题考场50‘
不过成绩也不是很差
得益于AC了第一题吧
先给出一道很久以前刷的题目
#include <cstdio>#include <string>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define str stringconst int maxlen = 1000 + 5;str st1, st2;int tot, f[maxlen][maxlen];int Min(int a, int b) { return a < b ? a : b; }int main(){ freopen("drdrd.in", "r", stdin); freopen("drdrd.out", "w", stdout); while (cin >> st1 >> st2) { memset(f, 127, sizeof(f)); int len1 = (int) st1.size(), len2 = (int) st2.size(); for (int i = 0; i <= len1; ++i)//注意检查边界条件 { f[i][0] = 0; for (int j = 0; j <= len2; ++j) f[i + 1][j + 1] = Min(f[i + 1][j + 1], f[i][j] + (st1[i] != st2[j])), i < len1 ? f[i + 1][j] = Min(f[i + 1][j], f[i][j] + 1) : 0, j < len2 ? f[i][j + 1] = Min(f[i][j + 1], f[i][j] + 1) : 0; } tot = INT_MAX; for (int i = 0; i <= len1; ++i) tot = Min(tot, f[i][len2]); cout << tot << endl; } return 0;}但是此题与编辑距离在输出结果时不同，取了min值
为什么呢？
“盾哥在所有操作之前会斟酌一下选择留下模板 A 的某一个最优的子串以保证操作次数尽量少（当然盾盾也可以全保留或一个都不留），这一步不计入操作次数”
即在我们做出所有操作之前（最开始）我们可以先处理A
且因为有“子串是指母串连续的一段”，即我们对第一个串只能从两头开始删（而不是从中间删）
所以有
for (int i = 0; i <= len1; ++i)
tot = Min(tot, f[i][len2]);
即处理了仅从A串的 1-i 变为B串，A串后全默认删除并找到min值
但似乎枚举也只处理了删除A串后面某段的情况而没有处理一开始就删除A串前面的某段
而实际上，初值f[i][0]=0,即默认A串前i个已经被删除才继续转移的
理解这点后，此题至此完美解决。