3813658_tle.cc

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

#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

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

//AAAA

inline string min(string a, string b)
{
	return a.length() < b.length() ? a : b;
}

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) + "(" + min(tmp, best[a][b]) + ")";
	return min(sub, ret);
}

int main()
{
	int length;
	int tmp, i, j, l;
	string sub;

	cin >> str;
	length = str.length();
	for (i = 0; i < length; i++)
	{
		for (j = 0; j < length; j++)
		{
			len[i][j] = length;
			best[i][j] = str;
		}
	}
	for (i = 0; i < length; i++)
	{
		len[i][i] = 1;
		best[i][i] = str.substr(i, 1);
	}
	for (l = 2; l <= length; l++)
	{
		for (i = 0; i <= length - l; i++)
		{
			sub = str.substr(i, l);
			best[i][i + l - 1] = sub;
			len[i][i + l - 1] = l;
			for (j = i; j < i + l; j++)
			{
				tmp = len[i][j] + len[j + 1][i + l - 1];
				if (tmp < len[i][i + l - 1])
				{
					len[i][i + l - 1] = tmp;
					best[i][i + l - 1] = best[i][j] + best[j + 1][i + l - 1];
				}
			}
			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][i + l - 1])
					{
						len[i][i + l - 1] = ret.length();
						best[i][i + l - 1] = ret;
					}
				}
			}
		}
	}
	cout << best[0][length - 1] << endl;
	return 0;
}