fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <stack>
  10. #include <queue>
  11. #include <list>
  12. #include <ctime>
  13. #include <math.h>
  14. #include <memory.h>
  15. #include <string.h>
  16. #include <stdlib.h>
  17.  
  18. using namespace std;
  19.  
  20. void ASS(bool b)
  21. {
  22. 	if (!b)
  23. 	{
  24. 		++*(int*)0;
  25. 	}
  26. }
  27.  
  28. #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
  29.  
  30. typedef long long LL;
  31. typedef vector<int> vi;
  32.  
  33. bool isCyclic(const char* s, int n, int len)
  34. {
  35. 	for (int i = len; i < n; ++i)
  36. 		if (s[i] != s[i - len])
  37. 			return false;
  38. 	return true;
  39. }
  40.  
  41. string Str(int x)
  42. {
  43. 	stringstream ss;
  44. 	ss << x;
  45. 	return ss.str();
  46. }
  47.  
  48. const int N = 107;
  49.  
  50. char s[N];
  51. string d[N][N];
  52.  
  53. /*
  54. string D(int L, int R)
  55. {
  56. 	if (L + 1 == R)
  57. 		return string(s + L, s + R);
  58. 	if (d[L][R].size())
  59. 		return d[L][R];
  60. 	string res = string(s + L, s + R);
  61. 	int n = R - L;
  62. 	for (int i = 1; i <= n; i++)
  63. 		if (n / i >= 2 && n % i == 0 && isCyclic(s + L, n, i))
  64. 		{
  65. 			string zip = Str(n / i) + "(" + D(L, L + i) + ")";
  66. 			if (res.size() > zip.size())
  67. 				res = zip;
  68. 		}
  69. 	for (int i = L + 1; i < R; i++) {
  70. 		string zip = D(L, i) + D(i, R);
  71. 		if (res.size() > zip.size())
  72. 			res = zip;
  73. 	}
  74. 	d[L][R] = res;
  75. 	return res;
  76. }
  77. */
  78.  
  79. void DPnonRec(int L, int R)
  80. {
  81. 	if (L + 1 == R)
  82. 	{
  83. 		d[L][R] = string(s + L, s + R);
  84. 		return;
  85. 	}
  86.  
  87. 	string res = string(s + L, s + R);
  88. 	int n = R - L;
  89. 	for (int i = 1; i <= n; i++)
  90. 		if (n / i >= 2 && n % i == 0 && isCyclic(s + L, n, i))
  91. 		{
  92. 			string zip = Str(n / i) + "(" + d[L][L + i] + ")";
  93. 			if (res.size() > zip.size())
  94. 				res = zip;
  95. 		}
  96. 	for (int i = L + 1; i < R; i++) {
  97. 		string zip = d[L][i] + d[i][R];
  98. 		if (res.size() > zip.size())
  99. 			res = zip;
  100. 	}
  101. 	d[L][R] = res;
  102. }
  103.  
  104.  
  105. string Solve()
  106. {
  107. 	int n = (int)strlen(s);
  108. 	//return D(0, n);
  109. 	for (int len = 1; len <= n; ++len)
  110. 		for (int i = 0; i + len <= n; ++i)
  111. 			DPnonRec(i, i + len);
  112. 	return d[0][n];
  113. }
  114.  
  115. int main()
  116. {
  117. 	cin >> s;
  118. 	cout << Solve() << "\n";
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0s 3528KB
comments (?)
stdin
copy 
NEERCYESYESYESNEERCYESYESYES
stdout
copy 
2(NEERC3(YES))
https://ideone.com/JfJEnr
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!