Uva11790 - Murcia's Skyline

題目大意

題目會給你一連串的高樓的高與寬
你要找出以高嚴格升序與嚴格降序的所有組合中，最寬的數字，並比較嚴格升序與嚴格降序哪個比較寬，輸出相對應格式的結果

重點觀念

• LIS
  • 參考 http://web.ntnu.edu.tw/~algo/Subsequence.html

分析

• 因為要得到最寬的所以不能優畫(length 有權重)，只能用 O(n^2) 的做法

程式題目碼

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int n;
        cin >> n;

        int h[n], w[n];

        for (int i = 0; i < n; i++) {
            cin >> h[i];
        }

        for (int i = 0; i < n; i++) {
            cin >> w[i];
        }

        int lis[n];
        int lds[n];
        for (int i = 0; i < n; i++) {
            lis[i] = w[i];
            lds[i] = w[i];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (h[j] < h[i]) {
                    lis[i] = max(lis[i], lis[j] + w[i]);
                }
                if (h[j] > h[i]) {
                    lds[i] = max(lds[i], lds[j] + w[i]);
                }
            }
        }

        int max_i = 0;
        int max_d = 0;

        for (int i = 0; i < n; i++) {
            max_i = max(max_i, lis[i]);
            max_d = max(max_d, lds[i]);
        }

        cout << "Case " << t << ". ";

        if (max_i >= max_d) {
            cout << "Increasing (" << max_i << "). Decreasing (" << max_d << ").";
        } else {
            cout << "Decreasing (" << max_d << "). Increasing (" << max_i << ").";
        }
        cout << endl;
    }
    return 0;
}