Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //#define int long long
- const long long INF = 1e9 + 7;
- const int MAXN = 200 + 10;
- const int N = 1e5 + 10;
- int last[MAXN][MAXN], rem[MAXN][MAXN];
- vector<int> ans;
- void get_ans(int l, int r, bool flag = false) {
- if (!flag) {
- if (last[l][r] == l) {
- get_ans(l, r, true);
- return;
- }
- get_ans(l, last[l][r], flag);
- get_ans(last[l][r], r, flag);
- } else {
- if (rem[l][r] == l) {
- return;
- }
- get_ans(l, rem[l][r], flag);
- get_ans(rem[l][r], r, flag);
- ans.emplace_back(rem[l][r] + 1);
- }
- }
- void solve() {
- int n;
- cin >> n;
- vector<int> a(n);
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- rem[i][j] = INF;
- }
- }
- for (int i = 0; i + 1 < n; ++i) {
- rem[i][i + 1] = i;
- }
- for (int len = 3; len <= n; ++len) {
- for (int l = 0; l + len - 1 < n; ++l) {
- int r = l + len - 1;
- for (int m = l + 1; m < r; ++m) {
- if (rem[l][m] != INF && rem[m][r] != INF) {
- if (a[m] > a[l] && a[m] > a[r] || a[m] < a[l] && a[m] < a[r]) {
- rem[l][r] = m;
- }
- }
- }
- }
- }
- int dp[n][n];
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- dp[i][j] = INF;
- last[i][j] = INF;
- }
- }
- for (int len = 2; len <= n; ++len) {
- for (int l = 0; l + len - 1 < n; ++l) {
- int r = l + len - 1;
- if (a[l] > a[r]) {
- continue;
- }
- if (rem[l][r] != INF) {
- dp[l][r] = len - 2;
- last[l][r] = l;
- }
- for (int m = l + 1; m < r; ++m) {
- if (a[m] < a[l] || a[m] > a[r]) {
- continue;
- }
- if (dp[l][r] > dp[l][m] + dp[m][r]) {
- dp[l][r] = dp[l][m] + dp[m][r];
- last[l][r] = m;
- }
- }
- }
- }
- if (last[0][n - 1] == INF) {
- cout << -1 << '\n';
- } else {
- get_ans(0, n - 1, false);
- cout << ans.size() << '\n';
- for (auto& i: ans) {
- cout << i << '\n';
- }
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int tt = 1;
- // cin >> tt;
- while (tt--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment