题目链接：1371 - Period
题意：给定两个字符串，可以把第二个字符串分成若干份，然后由第一个字符串去操作得到每个分出来的字符串，代价为其中的最大值，要求代价的最小值 思路：第一个字符串长度为50，所以答案肯定不会超过50，可以二分答案0到50，不二分的话直接就超时了，然后每次判断进行dp操作，类似LCS问题，只不过原来是相同的+1，现在变成不同的+1，因为不同的肯定就要进行操作了，然后有一个地方就是判断分割的位置，当dp[i][m] <= mid的时候，说明可以在该位置进行一个分段，令dp[i][0] = 0。 代码：#include#include #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\n", l); } return 0; }