Fshl0

Subsequence Reversal

May 31st, 2021 (edited)
342
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 = 50 + 9;
  6.  
  7. int dp[N][N][N][N], A[N];
  8.  
  9. int Go (int l, int r, int mn, int mx) {
  10.     if (dp[l][r][mn][mx] != -1)
  11.         return dp[l][r][mn][mx];
  12.     if (l > r)
  13.         return 0;
  14.     if (l == r)
  15.         return A[l] >= mn && A[l] <= mx;
  16.     int ret = 0;
  17.     ret = max (ret, max (Go (l + 1, r, mn, mx), Go (l, r - 1, mn, mx)));
  18.     if (A[l] >= mn && A[l] <= mx) {
  19.         ret = max (ret, 1 + Go (l + 1, r, A[l], mx));
  20.         ret = max (ret, 1 + Go (l + 1, r - 1, mn, A[l]));
  21.     }
  22.     if (A[r] >= mn && A[r] <= mx) {
  23.         ret = max (ret, 1 + Go (l, r - 1, mn, A[r]));
  24.         ret = max (ret, 1 + Go (l + 1, r - 1, A[r], mx));
  25.     }
  26.     ret = max (ret, Go (l + 1, r - 1, mn, mx));
  27.     if (A[r] >= mn && A[l] <= mx && A[r] <= A[l])
  28.         ret = max (ret, 2 + Go (l + 1, r - 1, A[r], A[l]));
  29.     return dp[l][r][mn][mx] = ret;
  30. }
  31.  
  32. int main () {
  33.     freopen ("subrev.in", "r", stdin);
  34.     freopen ("subrev.out", "w", stdout);
  35.     int n;
  36.     cin >> n;
  37.     for (int i = 1; i <= n; i++)
  38.         cin >> A[i];
  39.     memset (dp, -1, sizeof (dp));
  40.     cout << Go (1, n, 1, 50) << "\n";
  41.     return 0;
  42. }
  43.  
RAW Paste Data