Salvens

F

Aug 4th, 2023
1,952
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5.  
  6. //#define int long long
  7.  
  8. const long long INF = 1e9 + 7;
  9. const int MAXN = 200 + 10;
  10. const int N = 1e5 + 10;
  11.  
  12. int last[MAXN][MAXN], rem[MAXN][MAXN];
  13. vector<int> ans;
  14.  
  15. void get_ans(int l, int r, bool flag = false) {
  16.     if (!flag) {
  17.         if (last[l][r] == l) {
  18.             get_ans(l, r, true);
  19.             return;
  20.         }
  21.         get_ans(l, last[l][r], flag);
  22.         get_ans(last[l][r], r, flag);
  23.     } else {
  24.         if (rem[l][r] == l) {
  25.             return;
  26.         }
  27.         get_ans(l, rem[l][r], flag);
  28.         get_ans(rem[l][r], r, flag);
  29.         ans.emplace_back(rem[l][r] + 1);
  30.     }
  31. }
  32.  
  33. void solve() {
  34.     int n;
  35.     cin >> n;
  36.     vector<int> a(n);
  37.     for (int i = 0; i < n; ++i) {
  38.         cin >> a[i];
  39.     }
  40.     for (int i = 0; i < n; ++i) {
  41.         for (int j = 0; j < n; ++j) {
  42.             rem[i][j] = INF;
  43.         }
  44.     }
  45.     for (int i = 0; i + 1 < n; ++i) {
  46.         rem[i][i + 1] = i;
  47.     }
  48.     for (int len = 3; len <= n; ++len) {
  49.         for (int l = 0; l + len - 1 < n; ++l) {
  50.             int r = l + len - 1;
  51.             for (int m = l + 1; m < r; ++m) {
  52.                 if (rem[l][m] != INF && rem[m][r] != INF) {
  53.                     if (a[m] > a[l] && a[m] > a[r] || a[m] < a[l] && a[m] < a[r]) {
  54.                         rem[l][r] = m;
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.     }
  60.  
  61.     int dp[n][n];
  62.  
  63.     for (int i = 0; i < n; ++i) {
  64.         for (int j = 0; j < n; ++j) {
  65.             dp[i][j] = INF;
  66.             last[i][j] = INF;
  67.         }
  68.     }
  69.  
  70.     for (int len = 2; len <= n; ++len) {
  71.         for (int l = 0; l + len - 1 < n; ++l) {
  72.             int r = l + len - 1;
  73.             if (a[l] > a[r]) {
  74.                 continue;
  75.             }
  76.             if (rem[l][r] != INF) {
  77.                 dp[l][r] = len - 2;
  78.                 last[l][r] = l;
  79.             }
  80.  
  81.             for (int m = l + 1; m < r; ++m) {
  82.                 if (a[m] < a[l] || a[m] > a[r]) {
  83.                     continue;
  84.                 }
  85.                 if (dp[l][r] > dp[l][m] + dp[m][r]) {
  86.                     dp[l][r] = dp[l][m] + dp[m][r];
  87.                     last[l][r] = m;
  88.                 }
  89.             }
  90.         }
  91.     }
  92.     if (last[0][n - 1] == INF) {
  93.         cout << -1 << '\n';
  94.     } else {
  95.         get_ans(0, n - 1, false);
  96.         cout << ans.size() << '\n';
  97.         for (auto& i: ans) {
  98.             cout << i << '\n';
  99.         }
  100.     }
  101. }
  102.  
  103. signed main() {
  104.     ios_base::sync_with_stdio(false);
  105.     cin.tie(nullptr);
  106.     cout.tie(nullptr);
  107.  
  108.     int tt = 1;
  109. //    cin >> tt;
  110.     while (tt--) {
  111.         solve();
  112.     }
  113. }
Advertisement
Add Comment
Please, Sign In to add comment