UVA 1371

题目链接：1371 - Period

题意：给定两个字符串。能够把第二个字符串分成若干份，然后由第一个字符串去操作得到每一个分出来的字符串，代价为当中的最大值，要求代价的最小值

思路：第一个字符串长度为50，所以答案肯定不会超过50，能够二分答案0到50，不二分的话直接就超时了，然后每次推断进行dp操作。类似LCS问题，仅仅只是原来是同样的+1，如今变成不同的+1，由于不同的肯定就要进行操作了，然后有一个地方就是推断切割的位置，当dp[i][m] <= mid的时候，说明能够在该位置进行一个分段，令dp[i][0] = 0。

代码：

#include <stdio.h>
#include <string.h>

#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
const int INF = 0x3f3f3f3f;
const int N = 5005;
const int M = 55;

int t, n, m, dp[N][M];
char a[N], b[M];

bool judge(int mid) {
	memset(dp, INF, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i <= n; i++) {
		if (dp[i][m] <= mid)
			dp[i][0] = 0;
		for (int j = 0; j <= m; j++) {
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + (a[i + 1] != b[j + 1]));
			dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
		}
	}
	return dp[n][m] <= mid;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%s", b + 1);
		scanf("%s", a + 1);
		n = strlen(a + 1);
		m = strlen(b + 1);
		int l = 0, r = m;
		while (l < r) {
			int mid = (l + r) / 2;
			if (judge(mid)) r = mid;
			else l = mid + 1;
		}
		printf("%d
", l);
	}
	return 0;
}