SHARE
TWEET

Untitled

a guest Nov 21st, 2019 77 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. const int INF = 1e9;
  5.  
  6. vector<vector<int> > dp, forever, deleting;
  7. vector<int> ans;
  8.  
  9. bool can_delete(int h1, int h2, int h3) {
  10.     return ((h1 < h2 && h3 < h2) || (h1 > h2 && h3 > h2));
  11. }
  12.  
  13. void clean_all(int a, int b) {
  14.     assert(deleting[a][b] >= 0);
  15.     if (deleting[a][b] == a) return;
  16.     clean_all(a, deleting[a][b]);
  17.     clean_all(deleting[a][b], b);
  18.     ans.push_back(deleting[a][b]);
  19. }
  20.  
  21. void make_ans(int a, int b) {
  22.     assert(forever[a][b] >= 0);
  23.     if (forever[a][b] == a) {
  24.         clean_all(a, b);
  25.         return;
  26.     }
  27.     make_ans(a, forever[a][b]);
  28.     make_ans(forever[a][b], b);
  29. }
  30.  
  31. int main() {
  32.     int n;
  33.     cin >> n;
  34.     dp.resize(n, vector<int>(n, INF));
  35.     deleting.resize(n, vector<int>(n, -1));
  36.     forever.resize(n, vector<int>(n, -1));
  37.     vector<int> h(n);
  38.     for (int i = 0; i < n; ++i) {
  39.         cin >> h[i];
  40.     }
  41.     for (int i = 0; i + 1 < n; ++i) {
  42.         deleting[i][i + 1] = i;
  43.     }
  44.     for (int len = 2; len < n; ++len)
  45.         for (int i = 0; i + len < n; ++i) {
  46.             int j = i + len;
  47.             for (int a = i + 1; a < j; ++a)
  48.                 if (deleting[i][a] >= 0 && deleting[a][j] >= 0 && can_delete(h[i], h[a], h[j])) {
  49.                     deleting[i][j] = a;
  50.                     break;
  51.                 }
  52.         }
  53.  
  54.     for (int len = 1; len < n; ++len)
  55.         for (int i = 0; i + len < n; ++i) {
  56.             int j = i + len;
  57.             if (h[i] > h[j]) continue;
  58.             if (deleting[i][j] >= 0) {
  59.                 dp[i][j] = j - i - 1;
  60.                 forever[i][j] = i;
  61.             }
  62.             for (int k = i + 1; k < j; ++k) {
  63.                 if (h[i] > h[k] || h[j] < h[k]) continue;
  64.                 int check = dp[i][k] + dp[k][j];
  65.                 if (dp[i][j] > check) {
  66.                     dp[i][j] = check;
  67.                     forever[i][j] = k;
  68.                 }
  69.             }
  70.         }
  71.     int i = 0, j = n - 1;
  72.     if (forever[i][j] < 0) cout << -1;
  73.     else {
  74.         make_ans(i, j);
  75.         cout << ans.size() << "\n";
  76.         for (auto i : ans) {
  77.             cout << i + 1 << "\n";
  78.         }
  79.     }
  80.     return 0;
  81. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top