程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 1371 - Period(DP)

UVA 1371 - Period(DP)

編輯:C++入門知識

題目鏈接: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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved