fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define ff first
  8. #define ss second
  9.  
  10. typedef long long int ll;
  11. typedef vector< pair<int, int> > vii;
  12. typedef vector<int> vi;
  13. typedef vector<vi> vvi;
  14. typedef vector<long long int> vll;
  15. typedef pair<int, int> pii;
  16.  
  17. const ll INF = 1e18;
  18. const int inf = 1e9;
  19. const int MOD = 1e9 + 7;
  20. const int nax = 1000000 + 10;
  21.  
  22. int n, arr[nax];
  23. string s;
  24.  
  25. bool is1(int a, int b, string s1)
  26. {
  27.     int start = 0;
  28.     for(int i = a; i <= b; i++)
  29.         if(s[i] != s1[start++]) return false;
  30.     return true;
  31. }
  32. bool is(int cur, string s1)
  33. {
  34.     int len = s1.length();
  35.     int i = 0, j = len - 1;
  36.     while(j <= cur)
  37.     {
  38.         if(is1(i, j, s1))
  39.             return true;
  40.         i++, j++;
  41.     }
  42.     return false;
  43. }
  44. map< pair<int, string>, int> dp;
  45.  
  46. int solve(int cur, string cip)
  47. {
  48.     //cout << cur << " " << cip << endl;
  49.     if(cur >= n - 1) return 0;
  50.     if(dp.count(mp(cur, cip)))
  51.         return dp[mp(cur, cip)];
  52.     int ans = 1 + solve(cur + 1, cip);
  53.     string abhi = "";
  54.     for(int j = cur + 1; j < n; j++)
  55.     {
  56.         abhi += s[j];
  57.         if(is(cur, abhi) && cip != abhi)
  58.             ans = min(ans, 2 + solve(cur + (int)abhi.length(), abhi));
  59.     }
  60.     if(cip.length() > 0)
  61.     {
  62.         int len = cip.length();
  63.         if(is1(cur + 1, cur + len, cip))
  64.             ans = min(ans, 1 + solve(cur + len, cip));
  65.     }
  66.     return dp[mp(cur, cip)] = ans;
  67. }
  68. int main()
  69. {
  70.     ios::sync_with_stdio(0);
  71.     freopen("inp.in", "r", stdin);
  72.     freopen("out.txt", "w", stdout);
  73.     int t, tt = 0;
  74.     cin >> t;
  75.     while(t--)
  76.     {
  77.         dp.clear();
  78.         tt++;
  79.         cin >> s;
  80.         n = s.length();
  81.         string emp = "";
  82.         cout << "Case #" << tt << ": " << solve(-1, emp) << endl;
  83.     }
  84.     return 0;
  85. }
  86.  
Runtime error #stdin #stdout #stderr 0s 19152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/pixvWn
language:
C++ (gcc 8.3)
created:
6 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!