Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2011
1,731
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <string>
  8. #include <vector>
  9. #include <queue>
  10. #include <list>
  11.  
  12. using namespace std;
  13.  
  14. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  15. #define pb push_back
  16. #define mp make_pair
  17. #define TASKNAME "oaks"
  18.  
  19. typedef long long ll;
  20.  
  21. typedef vector<ll> vll;
  22. typedef vector<int> vi;
  23. typedef vector<vi> vvi;
  24. typedef vector<bool> vb;
  25.  
  26. const int INF = 1e9;
  27.  
  28. bool can(int h1, int h2, int h3) {
  29.   if (h1 < h2 && h3 < h2) return true;
  30.   if (h1 > h2 && h3 > h2) return true;
  31.   return false;
  32. }
  33.  
  34. vvi del;
  35. vvi dyn, fr;
  36. vi ans;
  37.  
  38.    
  39. int main() {
  40.   freopen(TASKNAME ".in", "r", stdin);
  41.   freopen(TASKNAME ".out", "w", stdout);
  42.  
  43.   int n;
  44.   while (scanf("%d", &n) >= 1) {
  45.     vi h(n);
  46.     for (int i = 0; i < n; i++) scanf("%d", &h[i]);
  47.  
  48.     del = vvi(n, vi(n, -1));
  49.     for (int a = 0; a + 1 < n; a++)
  50.       del[a][a + 1] = a;
  51.  
  52.     for (int l = 2; l < n; l++)
  53.       for (int a = 0; a + l < n; a++) {
  54.         int b = a + l;
  55.         for (int i = a + 1; i < b; i++)
  56.           if (del[a][i] >= 0 && del[i][b] >= 0 && can(h[a], h[i], h[b])) {
  57.             del[a][b] = i;
  58.             break;
  59.           }
  60.       }
  61.  
  62.     dyn = vvi(n, vi(n, INF));
  63.     fr = vvi(n, vi(n, -1));
  64.     for (int l = 1; l < n; l++)
  65.       for (int a = 0; a + l < n; a++) {
  66.         int b = a + l;
  67.         if (h[a] > h[b]) continue;
  68.         if (del[a][b] >= 0) {
  69.           dyn[a][b] = b - a - 1;
  70.           fr[a][b] = a;
  71.         }
  72.  
  73.         for (int i = a + 1; i < b; i++) {
  74.           if (h[a] > h[i] || h[i] > h[b]) continue;
  75.           int cans = dyn[a][i] + dyn[i][b];
  76.           if (dyn[a][b] > cans) {
  77.             dyn[a][b] = cans;
  78.             fr[a][b] = i;
  79.           }
  80.         }
  81.       }
  82.  
  83.     int a = 0, b = n - 1;
  84.     if (fr[0][n - 1] < 0) printf("-1\n");
  85.     else {
  86.       ans = vi();
  87.       addAns(a, b);
  88.       printf("%d\n", ans.size());
  89.       for (int i = 0; i < ans.size(); i++)
  90.         printf("%d\n", ans[i] + 1);
  91.     }
  92.  
  93.     #ifndef DEBUG
  94.     break;
  95.     #endif
  96.   }
  97.   return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement