题意:
看白书
要点:
白书上的题,还是有些难度的,具体分析看书吧,难点就是要求res[i][j]。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define maxn 5005
#define inf 0x3f3f3f3f
char str1[maxn], str2[maxn];
int len1, len2;
int dp[maxn][maxn], first[27][2], last[27][2], res[maxn][maxn];void init()
{int i, j, k;memset(last, -1, sizeof(last));memset(first, inf, sizeof(first));len1 = strlen(str1);len2 = strlen(str2);for (i = 0; i < len1; i++)//在字符串中找最先和最后出现的位置{if (first[str1[i] - 'A'][0] == inf)first[str1[i] - 'A'][0] = i;last[str1[i] - 'A'][0] = i;}for (i = 0; i < len2; i++){if (first[str2[i] - 'A'][1] == inf)first[str2[i] - 'A'][1] = i;last[str2[i] - 'A'][1] = i;}for(i=0;i<=len1;i++)for (j = 0; j <=len2; j++){int cnt = 0;for (k = 0; k < 26; k++){if (first[k][0] == inf && first[k][1] == inf)//两个字符串中均无此字符continue;if (first[k][0] > i - 1 && first[k][1] > j - 1)//最先出现的位置在后面,自己不算continue;if (last[k][0] <= i-1&&last[k][1] <= j-1)//最后出现的位置在前面,说明已经匹配continue;cnt++;}res[i][j] = cnt;}
}int main()
{int t,i,j;scanf("%d", &t);while (t--){scanf("%s%s", str1, str2);init();dp[len1][len2] = 0;for (i = len1 - 1; i >= 0; i--)dp[i][len2] = dp[i + 1][len2] + res[i][len2];//初始化,第二个字符串都不使用for (i = len2 - 1; i >= 0; i--)dp[len1][i] = dp[len1][i + 1] + res[len1][i];for (i = len1 - 1; i >= 0; i--)for (j = len2 - 1; j >= 0; j--)dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + res[i][j];printf("%d\n", dp[0][0]);}return 0;
}