2013年8月11日

UVa 11790 - Murcia's Skyline

#include <cstdio>

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    int h[9999], w[9999];
    for (int i = 0; i < N; i++) {
      scanf("%d", &h[i]);
    }
    int up[9999] = {}, down[9999] = {};
    for (int i = 0; i < N; i++) {
      scanf("%d", &w[i]);
      up[i] = down[i] = w[i];
    }
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        if (h[j] > h[i] && up[i] + w[j] > up[j]) {
          up[j] = up[i] + w[j];
        }
        if (h[j] < h[i] && down[i] + w[j] > down[j]) {
          down[j] = down[i] + w[j];
        }
      }
    }
    int inc = 0, dec = 0;
    for (int i = 0; i < N; i++) {
      inc = up[i] > inc ? up[i] : inc;
      dec = down[i] > dec ? down[i] : dec;
    }
    printf("Case %d. ", C++);
    if (inc >= dec) {
      printf("Increasing (%d). Decreasing (%d).\n", inc, dec);
    } else {
      printf("Decreasing (%d). Increasing (%d).\n", dec, inc);
    }
  }
  return 0;
}

沒有留言:

張貼留言