串折叠 Folding

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

$$\begin{gathered} dp[i][i]=1 \\ dps[i][i]=S[i] \end{gathered}$$

转移方程：

1. $$dp[i][j]=min(dp[i][k]+dp[k+1][j])(i\le k<j)$$
   经典的区间$dp$枚举中转点，那么相应的：
   $$\begin{gathered} if(dp[i][j]>dp[i][k]+dp[k+1][j] \\ dps[i][j]=dps[i][k]+dps[k+1][j] \end{gathered}$$
2. $$\begin{gathered} if(IsCircular(i,j,Len) \\ dp[i][j]=min(dp[i][j],dp[i][i+Len-1]+2+Digit[Section/Len])(1\le Len\le Section) \end{gathered}$$
   如果从$i$开始到$j$是一个循环节长度为$Len$的循环，那么$dp[i][j]$可以压缩，$dp[i][i+Len-1]$表示从i到第一个循环节结束，$+2$表示加上括号的长度，而$Section$为当前枚举的区间的长度，那么$Section/Len$即为区间长度除以单个循环节长度得到循环节数量，而$Digit[Section/Len]$则表示这个数量的位数，如1的位数是1，10的位数是2。那么相应的：
   $$\begin{gathered} if(dp[i][j]>dp[i][i+Len-1]+2+Digit[Section/Len] \\ dps[i][j]=to\mathrm{\_}string(Section/Len){+}^{\prime }{(}^{\prime }+dps[i][k]{+}^{\prime }{)}^{\prime } \end{gathered}$$
   个数+’(‘+循环节内容+’)’。
   AC代码：

   #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;
   }