fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define pli pair<ll,int>
  14. #define vi vector<int>
  15.  
  16. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef unsigned int ui;
  22.  
  23. using namespace std;
  24.  
  25. const int M = 1e9 + 7;
  26. const int INF = 1e9 + 7;
  27. const ll INFLL = (ll)2e18 + 7LL;
  28. const ld PI = acos(-1);
  29.  
  30. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  31. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  32.  
  33. template<class _, class __>
  34.     bool minimize(_ &x, const __ y){
  35.         if(x >= y){
  36.             x = y;
  37.             return true;
  38.         } else return false;
  39.     }
  40. template<class _, class __>
  41.     bool maximize(_ &x, const __ y){
  42.         if(x <= y){
  43.             x = y;
  44.             return true;
  45.         } else return false;
  46.     }
  47.  
  48. template<class _,class __>
  49.     void Add(_ &x, const __ y) {
  50.         x += y;
  51.         if (x >= M) {
  52.             x -= M;
  53.         }
  54.         return;
  55.     }
  56.  
  57. template<class _,class __>
  58.     void Diff(_ &x, const __ y) {
  59.         x -= y;
  60.         if (x < 0) {
  61.             x += M;
  62.         }
  63.         return;
  64.     }
  65.  
  66. //--------------------------------------------------------------
  67.  
  68. const int MaxN = 207;
  69.  
  70. int n,f[MaxN][MaxN],dp[MaxN][MaxN],len[MaxN];
  71. pii trace[MaxN][MaxN];
  72. char s[MaxN];
  73. vi uoc[MaxN];
  74.  
  75. string ToStr(int a) {
  76.     string s;
  77.     while (a) {
  78.         s = (char)(a%10 + 48) + s;
  79.         a /= 10;
  80.     }
  81.     return s;
  82. }
  83.  
  84. void prepare() {
  85.     memset(dp,0,sizeof(dp));
  86.     for (int i=1;i<=9;i++) len[i] = 3;
  87.     for (int i=10;i<=99;i++) len[i] = 4;
  88.     for (int i=100;i<=200;i++) len[i] = 5;
  89.     for (int i=1;i<=200;i++) {
  90.         for (int j=i;j<=200;j += i) {
  91.             uoc[j].pb(i);
  92.         }
  93.     }
  94.     for (int i=n;i>=1;i--) {
  95.         for (int j=n;j>=1;j--) {
  96.             if (s[i] == s[j]) dp[i][j] = dp[i+1][j+1] + 1;
  97.         }
  98.     }
  99. }
  100.  
  101. string Get(int l,int r) {
  102.     string res;
  103.     if (trace[l][r].fi == 0) {
  104.         res.resize(r - l + 1);
  105.         for (int i=l;i<=r;i++) {
  106.             res[i-l] = s[i];
  107.         }
  108.         return res;
  109.     }
  110.     if (trace[l][r].fi == 1) {
  111.         res = Get(l,trace[l][r].se) + Get(trace[l][r].se+1,r);
  112.         return res;
  113.     }
  114.     res = ToStr(trace[l][r].se) + '(' + Get(l,l + (r - l + 1)/trace[l][r].se - 1) + ')';
  115.     return res;
  116. }
  117.  
  118. bool check(int l,int r,int x) {
  119.     int leg = (r - l + 1)/x;
  120.     for (int i=l+leg;i<=r;i+=leg) {
  121.         if (dp[l][i] < leg) return false;
  122.     }
  123.     return true;
  124. }
  125.  
  126. void sol() {
  127.     cin >> n;
  128.     for (int i=1;i<=n;i++) cin >> s[i];
  129.     prepare();
  130.     for (int i=0;i<n;i++) {
  131.         for (int l=1;l<=n-i;l++) {
  132.             int r = l + i;
  133.             f[l][r] = r - l + 1;
  134.             for (int j=l;j<r;j++) {
  135.                 if (minimize(f[l][r],f[l][j] + f[j+1][r])) {
  136.                     trace[l][r] = mp(1,j);
  137.                 }
  138.             }
  139.             for (int x : uoc[r - l + 1]) {
  140.                 if (check(l,r,x) && minimize(f[l][r],len[x] + f[l][l + (r-l+1)/x - 1])) {
  141.                     trace[l][r] = mp(2,x);
  142.                 }
  143.             }
  144.         }
  145.     }
  146.     cout << Get(1,n);
  147. }
  148.  
  149. int main() {
  150. //	freopen("WSTRING.inp","r",stdin);
  151. //	freopen("WSTRING.out","w",stdout);
  152. 	FAST
  153. 	int t=1;
  154. //	cin >> t;
  155. 	while (t--) sol();
  156. }
  157.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7sz6FQ
language:
C++ (gcc 8.3)
created:
4 days 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!