Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <queue>
- #include <list>
- using namespace std;
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define pb push_back
- #define mp make_pair
- #define TASKNAME "oaks"
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- const int INF = 1e9;
- bool can(int h1, int h2, int h3) {
- if (h1 < h2 && h3 < h2) return true;
- if (h1 > h2 && h3 > h2) return true;
- return false;
- }
- vvi del;
- vvi dyn, fr;
- vi ans;
- int main() {
- freopen(TASKNAME ".in", "r", stdin);
- freopen(TASKNAME ".out", "w", stdout);
- int n;
- while (scanf("%d", &n) >= 1) {
- vi h(n);
- for (int i = 0; i < n; i++) scanf("%d", &h[i]);
- del = vvi(n, vi(n, -1));
- for (int a = 0; a + 1 < n; a++)
- del[a][a + 1] = a;
- for (int l = 2; l < n; l++)
- for (int a = 0; a + l < n; a++) {
- int b = a + l;
- for (int i = a + 1; i < b; i++)
- if (del[a][i] >= 0 && del[i][b] >= 0 && can(h[a], h[i], h[b])) {
- del[a][b] = i;
- break;
- }
- }
- dyn = vvi(n, vi(n, INF));
- fr = vvi(n, vi(n, -1));
- for (int l = 1; l < n; l++)
- for (int a = 0; a + l < n; a++) {
- int b = a + l;
- if (h[a] > h[b]) continue;
- if (del[a][b] >= 0) {
- dyn[a][b] = b - a - 1;
- fr[a][b] = a;
- }
- for (int i = a + 1; i < b; i++) {
- if (h[a] > h[i] || h[i] > h[b]) continue;
- int cans = dyn[a][i] + dyn[i][b];
- if (dyn[a][b] > cans) {
- dyn[a][b] = cans;
- fr[a][b] = i;
- }
- }
- }
- int a = 0, b = n - 1;
- if (fr[0][n - 1] < 0) printf("-1\n");
- else {
- ans = vi();
- addAns(a, b);
- printf("%d\n", ans.size());
- for (int i = 0; i < ans.size(); i++)
- printf("%d\n", ans[i] + 1);
- }
- #ifndef DEBUG
- break;
- #endif
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement