Fshl0

Modern Art 3

May 31st, 2021
830
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 300 + 9;
  6.  
  7. int rangeDP[N][N], A[N];
  8.  
  9. int main () {
  10.     int n;
  11.     cin >> n;
  12.     for (int i = 1; i <= n; i++)
  13.         cin >> A[i];
  14.     for (int i = 1; i <= n; i++)
  15.         rangeDP[i][i] = 0;
  16.     for (int len = 2; len <= n; len++) {
  17.         for (int i = 1; i + len - 1 <= n; i++) {
  18.             int j = i + len - 1;
  19.             rangeDP[i][j] = rangeDP[i][j - 1];
  20.             for (int k = i; k < j; k++)
  21.                 if (A[k] == A[j])
  22.                     rangeDP[i][j] = max (rangeDP[i][j], rangeDP[k + 1][j - 1] + rangeDP[i][k] + 1);
  23.         }
  24.     }
  25.     cout << n - rangeDP[1][n] << "\n";
  26.     return 0;
  27. }
  28.  
RAW Paste Data