Advertisement
Josif_tepe

Untitled

Apr 11th, 2023
509
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <map>
  5. using namespace std;
  6. const int maxn = 505;
  7. int zuma[maxn];
  8. int dp[maxn][maxn];
  9.  
  10. int rec(int i, int j) {
  11.     if(i > j) {
  12.         return 0;
  13.     }
  14.     if(i == j) {
  15.         return 1;
  16.     }
  17.     if(dp[i][j] != -1) {
  18.         return dp[i][j];
  19.     }
  20.     int res = 2e9;
  21.     res = min(res, rec(i + 1, j) + 1);
  22.     if(zuma[i] == zuma[i + 1]) {
  23.         res = min(res, rec(i + 2, j) + 1);
  24.     }
  25.     for(int k = i + 2; k <= j; k++) {
  26.         if(zuma[i] == zuma[k]) {
  27.             res = min(res, rec(i + 1, k - 1) + rec(k + 1, j));
  28.         }
  29.     }
  30.     return dp[i][j] = res;
  31. }
  32. int main() {
  33.     ios_base::sync_with_stdio(false);
  34.     int n;
  35.     cin >> n;
  36.    
  37.     for(int i = 0; i < n; i++) {
  38.         cin >> zuma[i];
  39.     }
  40.     memset(dp, -1, sizeof dp);
  41.     cout << rec(0, n - 1) << endl;
  42.     return 0;
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement