在这里插入图片描述
UVA1630
这是一个区间动态规划
定义：$dp[i][j]$为$i$到$j$的字符串能压缩成的最小长度，$dps[i][j]$保存$i$到$j$的字符串能压缩成的最短字符串，$S[i]$表示第$i$个字符（从1开始编号）。
初始化：

转移方程：

  1. 经典的区间$dp$枚举中转点，那么相应的：
  2. 如果从$i$开始到$j$是一个循环节长度为$Len$的循环，那么$dp[i][j]$可以压缩，$dp[i][i+Len-1]$表示从i到第一个循环节结束，$+2$表示加上括号的长度，而$Section$为当前枚举的区间的长度，那么$Section/Len$即为区间长度除以单个循环节长度得到循环节数量，而$Digit[Section/Len]$则表示这个数量的位数，如1的位数是1，10的位数是2。那么相应的：个数+’(‘+循环节内容+’)’。
    AC代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    #include<iostream>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<cmath>
    #include<map>
    using namespace std;
    string S;
    int Digit[101];
    int dp[101][101];
    string dps[101][101];
    //判断Left到Right区间是否是长度为Len的循环节的循环
    bool IsCircular(const int&Left, const int& Right, const int& Len) {
    	for (int i = Left; i <= Right; ++i) {
    		if (S[i] != S[(i - Left) % Len + Left]) {
    			return false;
    		}
    	}
    	return true;
    }
    void InitDigit() {
    	for (int i = 1; i <= 9; ++i) {
    		Digit[i] = 1;
    	}
    	for (int i = 10; i <= 99; ++i) {
    		Digit[i] = 2;
    	}
    	Digit[100] = 3;
    }
    int main() {
    	InitDigit();
    	while (cin >> S) {
    		S = ' ' + S;
    		memset(dp, 0x3f, sizeof(dp));
    		int&& n = S.size() - 1;
    		for (int i = 1; i <= n; ++i) {
    			dp[i][i] = 1;
    			dps[i][i] = S[i];
    		}
    		//枚举区间长度
    		for (int Section = 2; Section <= n; Section++) {
    			for (int i = 1, j = i + Section - 1; j <= n; i++, j++) {
    				for (int k = i; k < j; k++) {
    					if (dp[i][j] > dp[i][k] + dp[k + 1][j]) {
    						dp[i][j] = dp[i][k] + dp[k + 1][j];
    						dps[i][j] = dps[i][k] + dps[k + 1][j];
    					}
    				}
    				for (int k = i; k < j; k++) {
    					int&& Len = k - i + 1;
    					//区间要想形成循环，只能由整数倍个循环节组成
    					if (Section % Len != 0) {
    						continue;
    					}
    					if (IsCircular(i, j, Len)) {
    						if (dp[i][j] > dp[i][k] + 2 + Digit[Section / Len]) {
    							dp[i][j] = dp[i][k] + 2 + Digit[Section / Len];
    							dps[i][j] = to_string(Section / Len) + '(' + dps[i][k] + ')';
    						}
    					}
    				}
    			}
    		}
    		cout << dps[1][n] << endl;
    	}
    	return 0;
    }