POJ2176 Folding

描述

给定一个长度不超过100的字符串，求其“压缩”后长度最短的字符串。如有多个，输出任意即可。

其中对于一个字符串\(str\)的“压缩”\(F(str)\)定义如下：

当\(|str|=1\)时，有\(F(str)=str\),\(|F(str)|=1\)。
\(F(str_1+str_2)=F(str_1)+F(str_2)\)
\(X(str)\)是字符串\(\underbrace{str+str+\cdots+str}_X\)的压缩，且\(|X(str)|=\lfloor\lg X\rfloor+|str|+2\)，即包含括号和数字本身。

如字符串AAAAAAAAAABABABCCD的最短压缩为9(A)3(AB)CCD,长度由\(18\)降为\(12\)。注意2(C)的长度为\(4\)，不会比CC更优。

压缩可以嵌套。如AAAAAAABAAAAAAAABA可以压缩为2(7(A)BA)。

思路

设\(F(l,r)\)表示合并字符串\(S_{l\cdots r}\)得到的最短长度。根据定义，字符串的压缩具有叠加性，得到：

\[F(l,r) = \min\limits_{l \leq k < r}\{F(l,k) + F(k,r+1),\text{cost}(l,r)\}
\]

其中\(\text{cost}\)函数表示\(S_{l\cdots r}\)直接被压缩后的长度；若其不能被压缩，则返回\(\infty\)。

子串\((l,r)\)本身就可能被压缩。我们可以考虑从\(1\)至\(\frac{len}{2}\)枚举模式串的长度，如果匹配，则将压缩之后的字符串及其长度作为一个初始决策。之后再枚举合并子区间的价值就可以了。

代码

#include <cstdio>

#include <cstring>

#include <cctype>

using namespace std;

#define rg register

#define openFile(z) freopen(z".in", "r", stdin), freopen(z".out", "w", stdout)

typedef long long ll;

template<class type> inline type quickRead(type sample)

{

	type ret = 0, sign = 1; char ch = getchar();

	while(! isdigit(ch))

		sign = ch == '-' ? -1 : 1, ch = getchar();

	while(isdigit(ch))

		ret = ret * 10 + ch - '0', ch = getchar();

	return sign == -1 ? -ret : ret;

}

const int maxLen = 102;

const int Inf = 0x3f3f3f3f;

struct sub_string

{

	char str[maxLen];

	int len;

}F[maxLen][maxLen];

char template_string[maxLen];

int Len;

inline void break_point()

{}//用于debug

int main()

{

	openFile("POJ2176");

	scanf("%s", template_string + 1);

	Len = strlen(template_string + 1);

	for(rg int i = 1; i <= Len; ++ i)

	{

		F[i][i].str[0] = template_string[i],

		F[i][i].len = 1;

	}//初始化，单个字符的最短长度只能是1.

	for(rg int len = 2; len <= Len; ++ len)

	{

		for(rg int l = 1, r = len ; r <= Len; ++ l, ++ r)

		{

			F[l][r].len = Inf;

			for(rg int sub_string_len = 1; sub_string_len <= len >> 1; ++ sub_string_len)

			{

                //枚举模式串的长度并匹配

				if(len % sub_string_len != 0)

					continue;//优化：模式串的长度一定是原串的某个约数

				int match_left = l, match_right = l + sub_string_len;

				while(template_string[match_left] == template_string[match_right] && match_right <= r)

				{

					++ match_left;

					++ match_right;

				}

				if(match_right > r)//匹配成功

				{

					sprintf(F[l][r].str, "%d", (r - l + 1) / sub_string_len);

					strcat(F[l][r].str, "(");

					strcat(F[l][r].str, F[l][l + sub_string_len - 1].str);

					strcat(F[l][r].str, ")");

					F[l][r].len = strlen(F[l][r].str);//将“压缩自己”作为一个候选决策

					break;

				}

			}

			for(rg int k = l; k < r; ++ k)

			{

				if(F[l][k].len + F[k + 1][r].len < F[l][r].len)//枚举“合并区间”的决策

				{

					F[l][r].len = F[l][k].len + F[k + 1][r].len;

					strcpy(F[l][r].str, F[l][k].str);

					strcat(F[l][r].str, F[k + 1][r].str);

				}

			}

		}

	}

	puts(F[1][Len].str);

	return 0;

}

巴特西

POJ2176 Folding

POJ2176 Folding

描述

思路

代码

最新文章

热门文章