uva 1371 - Period(二分+dp)

題目鏈接：uva 1371 - Period

題目大意：給出兩個字符串A，B將B分解成若干個子字符串，然後每個子字符串都要變成字符串A，所有子串中編輯最多的次數即為當前狀態下的最大編輯次數，要求求最小的最大編輯次數。

解題思路：二分答案，用dp判斷，主要是dp判斷，dp[i][j]表示到1~i的字符串匹配到j的最大編輯次數，然後考慮分段的時候只要dp[i][0] < mid，那麼就可以將dp[i][0] 置0，表示做為起點。

#include 
#include 
#include 

using namespace std;
const int N = 5005;
const int M = 55;
const int INF = 0x3f3f3f3f;

char s[M], e[N];
int n, m, dp[N][M];

void init () {
	scanf("%s%s", s+1, e+1);
	n = strlen(e+1);
	m = strlen(s+1);
}

bool judge (int k) {
	memset(dp, INF, sizeof(dp));

	dp[0][0] = 0;
	for (int i = 0; i <= n; i++) {

		if (dp[i][m] <= k)
			dp[i][0] = 0;

		for (int j = 0; j <= m; j++) {
			if (dp[i][j] > k)
				continue;

			dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + (e[i+1] == s[j+1] ? 0 : 1));
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1);
			dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1);
		}
	}
	return dp[n][m] <= k;
}

int search() {
	int l = 0, r = m;
	while (l < r) {
		int mid = (l + r) / 2;

		if (judge(mid))
			r = mid;
		else
			l = mid + 1;
	}
	return l;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();
		printf("%d\n", search());
	}
	return 0;
}