uva 1351 區間dp

uva 1351 區間dp

UVA 1351 - String Compression

 

問一個字符串經過壓縮後最短可以到多短。壓縮規則是如果有連續的重復子串(如:abcabcabcad)可以壓縮成重復次數 + ( 重復子串) (前面例子的答案: 3(abc)ad )。壓縮後的串長度要把數字和括號計算在內。

區間dp，dp存該區間能壓縮的最小長度。
對於每個區間可以被分成兩個子區間，或者該區間可以壓縮。預處理出每個區間可以最多的由幾個子串重復組成:c[i][j]。

dp[i][j] = min{dp[i][k] + dp[k][j], digits(s) + dp[i][l] + 2};
l = (j-i+1)/c[i][j];
s = c[i][j];

而對於c數組的預處理可以O(n^3)完成。枚舉重復子串的長度和起始位置，然後從起始位置找，每找到一個串c[i][j]+1;具體見代碼。

 

 

 

#include 

using namespace std;

const int INF = 999999999;

int len;
char s[205];
int _c[205][205];
int dp[205][205];

int _degits(int num) {
	int cnt = 0;
	while (num) {
		cnt++;
		num /= 10;
	}
	return cnt;
}

void _solve() {
	for(int i=0; i0; T--) {
		scanf (%s, s);
		len = strlen(s);

		_solve();


		for (int i=0; i=0; i--) {
				dp[i][j] = INF;
				for (int k=i; k