fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <climits>
  5. #include <cstring>
  6. #include <utility>
  7. #include <vector>
  8. #include <string>
  9. #include <cstdio>
  10. #include <bitset>
  11. #include <ctime>
  12. #include <cmath>
  13. #include <stack>
  14. #include <list>
  15. #include <set>
  16. #include <map>
  17.  
  18. using namespace std;
  19.  
  20. #define sci stack <int>
  21. #define vci vector <int>
  22. #define vcs vector <string>
  23. #define vcd vector <double>
  24. #define vci64 vector <long long>
  25. #define seti set <int>
  26. #define mseti multiset <int>
  27.  
  28. const int maxn = 100 + 5;
  29.  
  30. typedef unsigned int uint;
  31. typedef long long int64;
  32. typedef unsigned long long uint64;
  33.  
  34. template <class T> inline T Sqr(const T & x) { return x * x; }
  35. template <class T> inline T Abs(const T & x) { return x > 0 ? x : -x; }
  36. template <class T> inline T Min(const T & a, const T & b) { return a < b ? a : b; }
  37. template <class T> inline T Max(const T & a, const T & b) { return a > b ? a : b; }
  38. template <class T> inline T Ksm(const T & a, const T & b, const T & m) { T _ = 1; for (; b; b >>= 1, a = a * a % m) (b & 1) ? _ = _ * a % m : 0; return _ % m; }
  39. template <class T> inline void Swap(T & a, T & b) { T _; _ = a; a = b; b = _; }
  40.  
  41. char str[maxn];
  42. int f[maxn][maxn];
  43. int bit[4] = { 0, 100, 10, 1 };
  44.  
  45. int getint()
  46. {
  47.    char ch = getchar(); int result = 0, res = 1;
  48.    for (; '0' > ch || ch > '9'; ch = getchar()) ch == '-' ? res = -1 : 0;
  49.    for (; '0' <= ch && ch <= '9'; result = result * 10 + ch - '0', ch = getchar());
  50.    return result * res;
  51. }
  52.  
  53. bool check(int l, int mid, int r)
  54. {
  55.    int lens, lent;
  56.    if ((lent = r - l + 1) % (lens = mid - l + 1) != 0) return 0;
  57.    for (int i = l + lens; i <= r; i += lens)
  58.       for (int j = 0; j <= lens - 1; ++j)
  59.          if (str[l + j - 1] != str[i + j - 1]) return 0;
  60.    return 1;
  61. }
  62.  
  63. int calc(int num)
  64. {
  65.    for (int i = 1; i <= 3; ++i)
  66.       if (num >= bit[i]) return 3 - i + 1;
  67.    return 0;
  68. }
  69.  
  70. int main()
  71. {
  72. #ifndef ONLINE_JUDGE
  73.    freopen("1090.in", "r", stdin);
  74.    freopen("1090.out", "w", stdout);
  75. #endif
  76.  
  77.    scanf("%s", str); int len = strlen(str);
  78.    memset(f, 1, sizeof(f));
  79.    for (int i = 1; i <= len; ++i) f[i][i] = 1;
  80.    for (int k = 1; k <= len; ++k)
  81.       for (int i = 1; i + k <= len; ++i)
  82.          for (int j = i, g = 0; j + 1 <= i + k; ++j)
  83.          {
  84.             f[i][i + k] = Min(f[i][i + k], f[i][j] + f[j + 1][i + k]);
  85.             if (check(i, j, i + k)) f[i][i + k] = 
  86.                Min(f[i][i + k], g = Min(calc((k + 1) / (j - i + 1)) + 2 + f[i][j], k + 1));
  87.          }
  88.    printf("%d\n", f[1][len]);
  89.  
  90.    return 0;
  91. }
Success #stdin #stdout 0.01s 2768KB
comments (?)
stdin 
NEERCYESYESYESNEERCYESYESYES
stdout 
14
https://ideone.com/yG3PHG
language:
C++ (gcc 8.3)
created:
11 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!