fork download
copy 
  1. /*
  2.          Author: Nguyen Tran Tuan Tu - A2-K68 - Ngo Quyen High school
  3.          Training VOI 2026
  4. */
  5. #include <bits/stdc++.h>
  6. // #include<ext/pb_ds/assoc_container.hpp>
  7. // #include<ext/pb_ds/tree_policy.hpp>
  8. // #pragma GCC optimize("O2", "unroll-loops", "Ofast")
  9. // #pragma GCC target("avx,avx2,fma")
  10. // #pragma GCC optimize("unroll-loops,02,no-stack-protector")
  11. // #pragma GCC optimize("O3,unroll-loops")
  12. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  13.  
  14. // input/output
  15. #define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  16. #define el cout << '\n'
  17. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  18.  
  19. //data type
  20. #define int128 __uint128_t
  21. #define ll long long
  22. #define ull unsigned long long
  23. #define pii pair<int, int>
  24. #define pll pair<ll, ll>
  25. #define piv pair<int, vector<int>>
  26. #define vi vector<int>
  27. #define vl vector<ll>
  28. #define vc vector<char>
  29.  
  30. //STL
  31. #define sz(x) (int)(x).size()
  32. #define for1(i,l,r) for(auto i = l; i <= r; i++)
  33. #define for2(i,r,l) for(auto i = r; i >= l; i--)
  34. #define for3(i,l,r) for(auto i = l; i < r; i++)
  35. #define for4(i,r,l) for(auto i = r; i > l; i--)
  36. #define forec(i,a) for(auto i : a)
  37. #define pb push_back
  38. #define eb emplace_back
  39. #define pf push_front
  40. #define all(x) (x).begin(), (x).end()
  41. #define fi first
  42. #define se second
  43.  
  44. //bitmask
  45. #define bitcnt(n) __builtin_popcount(n)
  46. #define mask(i) (1 << (i))
  47. #define bit(n, i) (((n) >> (i)) & 1)
  48. #define set_on(n, i) ((n) | mask(i))
  49. #define set_off(n, i) ((n) & ~mask(i))
  50. #define all_subset(mask) (1 << mask)
  51. #define is_bit(pos, mask) ((mask >> pos) & 1)
  52. #define all(x) (x).begin(), (x).end()
  53.  
  54. //constant
  55. #define N 1000005
  56. #define MOD 998244353
  57. #define INF 0x3f3f3f3f
  58. #define LINF 0x3f3f3f3f3f3f3f3f
  59. const int mod = 1e9 + 7;
  60. const int d4x[4] = {-1, 0, 1, 0}, d4y[4] = {0, 1, 0, -1};
  61. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  62.  
  63. //using namespace chrono;
  64. //using namespace __gnu_pbds;
  65. using namespace std;
  66. /*----------------------------------------------------------------------------------------------------
  67.                                     NTTT_NgoQuyenHighSchool_A2_K68                                     */
  68. int n, dp[1000][1000];
  69. string s;
  70. void read(){
  71.     cin >> n >> s;
  72. }
  73.  
  74. /*----------------------------------------------------------------------------------------------------*/
  75.  
  76. void solve(){
  77.     for(int i = 0; i < n; i++){
  78.         dp[i][i] = 1;
  79.     }
  80.     for(int l = 2; l <= n; l++) {
  81.         for (int i = 0; i + l - 1 < n; i++) {
  82.             int j = i + l - 1;
  83.             if(s[i] == s[j]){
  84.                 dp[i][j] = dp[i][j - 1]+1;
  85.             }
  86.             for(int k = i; k < j; k++){
  87.                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
  88.             }
  89.         }
  90.     }
  91.     cout << dp[0][n - 1] << endl;
  92. }
  93.  
  94. /*----------------------------------------------------------------------------------------------------*/
  95. int main(){
  96.     #define NAME "TUANTU"
  97.     if(fopen(NAME".INP", "r")){
  98.         freopen(NAME".INP", "r", stdin);
  99.         freopen(NAME".OUT", "w", stdout);
  100.     }
  101.     fastIO;
  102.     int t = 1;
  103.     while(t--){
  104.         read();
  105.         solve();
  106.     }
  107.     return execute, 0;
  108. }
Success #stdin #stdout #stderr 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed: 0.004364s
https://ideone.com/FKxgCB
language:
C++ (gcc 8.3)
created:
13 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!