3813863_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <string>
//#include <time.h>
//#include <iostream>
#include <algorithm>

using namespace std;

string best[101][101];
int len[101][101];
string str;

inline string itoa(int t)
{
	char str[10];
	int c = 0;

	if (t == 0)
		return "0";
	while (t != 0)
	{
		char ch = (t % 10 + '0');
		t /= 10;
		str[c++] = ch;
	}
	str[c] = '\0';
	reverse(str, str + c);
	return string(str);
}

inline string check(string sub, int t, int l, int a, int b)
{
	string tmp = sub.substr(0, l);
	string ret = "";

	for (int i = 0; i < t; i++)
	{
		ret += tmp;
	}
	if (ret.compare(sub) == 0)
		return ret = itoa(t) + "(" + (l < len[a][b] ? tmp : best[a][b]) + ")";
	return sub;
}

int main()
{
	int length;
	int tmp, i, j, l, t, b;
	string sub;
	char chr[101];

	scanf("%s", chr);
	//double t1 = clock();
	str = string(chr);
	length = str.length();
	for (i = 0; i < length; i++)
	{
		len[i][i] = 1;
		best[i][i] = chr[i];
	}
	for (l = 2; l <= length; l++)
	{
		for (i = 0; i <= length - l; i++)
		{
			t = i + l - 1;
			sub = str.substr(i, l);
			best[i][t] = sub;
			len[i][t] = l;
			b = -1;
			for (j = i; j < i + l; j++)
			{
				tmp = len[i][j] + len[j + 1][t];
				if (tmp < len[i][t])
				{
					len[i][t] = tmp;
					b = j;
					//best[i][t] = best[i][j] + best[j + 1][t];
				}
			}
			if (b != -1)
			{
				best[i][t] = best[i][b] + best[b + 1][t];
			}
			for (j = 1; j < l; j++)
			{
				if (l % j == 0)
				{
					string ret = check(sub, l / j, j, i, i + j - 1);
					if (ret.length() < len[i][t])
					{
						len[i][t] = ret.length();
						best[i][t] = ret;
						break;
					}
				}
			}
		}
	}
	//double t2 = clock();
	//printf("%.0lf\n", t2 - t1);
	printf("%s\n", best[0][length - 1].c_str());
	return 0;
}