fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FOR(i,a,b)      for (int i = (a), _b = (b); i <= (_b); ++i)
  6. #define FORD(i,a,b)     for (int i = (a), _b = (b); i >= (_b); --i)
  7. #define REP(i, n)        for (int i = (0), _n = (n); i < _n; ++i)
  8. #define getBit(mask,i)  (((mask) >> (i)) & (1LL))
  9. #define MASK(x)            (1LL << (x))
  10. #define allof(x)        begin(x), end(x)
  11. #define el              cout << '\n';
  12.  
  13. //--Compare------------------------------------------------------------------------------------
  14. template<class X, class Y> 
  15.     inline bool maximize(X &x, const Y &y){ return (x < y) ? x = y, 1 : 0; }
  16.  
  17. template<class X, class Y> 
  18.     inline bool minimize(X &x, const Y &y){ return (x > y) ? x = y, 1 : 0; }
  19.  
  20. //--Process------------------------------------------------------------------------------------
  21.  
  22. // #define int             long long
  23.  
  24. string S;
  25. int n;
  26.  
  27. void loadInput(void)
  28. {
  29.     cin >> S;
  30.     n = S.size();
  31. }
  32.  
  33. namespace subtask2
  34. {
  35.     int dp[363][363];
  36.  
  37.     int dfs(int l, int r)
  38.     {
  39.         if (l >= r) return 1;
  40.         if (dp[l][r] != -1) return dp[l][r];
  41.  
  42.         int res = (S[l] == S[r] ? dfs(l + 1, r - 1) : 3636);
  43.         FOR(k, l, r - 1) minimize(res, dfs(l, k) + dfs(k + 1, r));
  44.  
  45.         return dp[l][r] = res;
  46.     }
  47.  
  48.     bool solve()
  49.     {
  50.  
  51.         memset(dp, -1, sizeof dp);
  52.  
  53.         cout << dfs(0, n - 1) << '\n';
  54.  
  55.         return cerr << "2\n", true;
  56.     }
  57. }
  58.  
  59. signed main(void)
  60. {
  61.     cin.tie(nullptr)->sync_with_stdio(false);
  62.     cin.exceptions(cin.failbit);
  63.  
  64.     int T; cin >> T;
  65.     while (T--) 
  66.     {
  67.         loadInput();
  68.  
  69.         // if (subtask1::solve()) continue;
  70.         if (subtask2::solve()) continue;
  71.     }
  72.  
  73.     cerr << (1.0 * clock() / CLOCKS_PER_SEC);
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin
copy 
3
aabcbda
abba
addbcba
stdout
copy 
3
1
2
stderr
copy 
2
2
2
0.006644
https://ideone.com/DD5bwI
language:
C++14 (gcc 8.3)
created:
2 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!