题意：
给字符串A，字符串B。有三种操作：1，在字符串的前端或后端加上一个字符2，删掉前端或后端一个字符，改变字符串中间一个字符。求将一个A的子串变成B最少的操作数。
思路：
我们要求A一个子串，和B的子串有着最大匹配
说一下最大匹配：这个可能是和B的子串相同，也有可能是和B的子串在中间有几个位置不同其他都相同。
我们再用B的长度减去最大匹配中相同的字符个数，得到答案
#include <iostream> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <queue> #include <set> using namespace std; typedef long long LL; typedef pair<int, int>PII; char a[2010], b[2010]; int f[2010][2010]; int main() { cin >> a + 1 >> b + 1; int lena = strlen(a + 1), lenb = strlen(b + 1); int res = 0; for (int i = 1; a[i]; i++) for (int j = 1; b[j]; j++) res = max(res, f[i][j] = f[i - 1][j - 1] + (a[i] == b[j])); cout << lenb - res << endl; return 0; }
题意：
福尔摩斯正在处理一件案子。此时已经抓捕了n个嫌疑人，里面只可能有一个是真正的犯人。福尔摩斯正在审问这些嫌疑人。
每个嫌疑人的回答只有两种，一种表明他说编号为i的嫌疑人不是犯人，用-i表示；另一种表明他说编号为i的嫌疑人是犯人，
用+i表示。聪明的福尔摩斯已经知道了其中有m个人说的是真话。要求那些人说的是真话，那些人说的是假话。
思路：
我们先假设某个人是嫌疑犯，然后统计真话的个数 如果等于给定的 那么这个就是一种可能的存在
#include <iostream> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <queue> #include <set> using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 100010; int n, m; char s[N];//+ - 号 int p[N]; int a[N], b[N];//说别人是嫌犯或不是嫌犯的总数 int ans[N]; int main() { cin >> n >> m; int sum = 0;//不是嫌犯的总数 for (int i = 0; i < n; i++) { cin >> s[i] >> p[i]; if (s[i] == ‘-‘) { b[p[i]] ++; sum++; } else a[p[i]] ++; } int res = 0; for (int i = 1; i <= n; i++)//假设i是嫌犯，统计真话的数量 { int m1 = a[i] + sum - b[i];//说这个人是嫌犯的都是真话，说其他人不是的也是真话 if (m1 == m)//统计集中可能的情况 { ans[i] = 1; res++; } } for (int i = 0; i < n; i++) { if (s[i] == ‘+‘) { if (ans[p[i]]) { if (res == 1) cout << "Truth" << endl;//如果只有一种可能 那么说这个人是的就一定是对的 else cout << "Not defined" << endl;//否则多种情况的情况下就是不确定的 } else { cout << "Lie" << endl;//如果都不是的话 那肯定是说谎的 因为这个人不存在是嫌疑犯的可能 } } else {//这里分析同上面 if (ans[p[i]]) { if (res == 1) cout << "Lie" << endl; else cout << "Not defined" << endl; } else cout << "Truth" << endl; } } return 0; }
原文：https://www.cnblogs.com/yctql/p/14866000.html