UVa10534 - Murcia’s Skyline(LIS, 動態規劃)

題目大意

摩天大樓一座有一座的蓋起，這時候許多摩天大樓在一起時會有一條天際線。
摩天大樓有不同的寬度、高度，我們想要找出 LIS 並且寬度要是最長的、LDS 並且寬度要是最長的

題目連結

重點觀念

• 了解甚麼時候使用時間複雜度 \(O(n^2)\) 的 LIS

分析

• 由於這題的 LIS 數值權重並非都相同，因此只能使用 \(O(n^2)\) 版
• 做一次 LIS 與 LDS，並找出最大值即可。

參考連結

Uva11790 - Murcia’s Skyline by txya900619
http://web.ntnu.edu.tw/~algo/Subsequence.html

心得

老實講，我其實已經太久沒有寫過 LIS 時間複雜度 \(O(n^2)\) 的版本了，都快忘記了…。
有時候演算法沒有到非常熟，忘了真的很難憑自己的記憶在馬上推出來，但是可以透過查看自己的筆記就可以馬上想出來。

還真希望我隨時都可以想到這些筆記XD。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1000020
#define int long long
using namespace std;
int t, n, kase = 0;
int height[MAXN], width[MAXN];
int lis[MAXN], lds[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    cin >> t;
    while(t--){
        //做動態規劃前，一定要先將陣列歸 0，才不會讓陣列裡面混入前面的資料
        memset(lis, 0, sizeof(lis)); 
        memset(lds, 0, sizeof(lds));
        cin >> n;
        for(int i = 0; i < n; i++) cin >> height[i];
        for(int i = 0; i < n; i++) cin >> width[i];

        //LIS 應用
        for(int i = 0; i < n; i++){
            lis[i] = width[i];
            lds[i] = width[i];
            for(int j = 0; j < i; j++){
                if(height[i] > height[j]) lis[i] = max(lis[i], lis[j] + width[i]);
                if(height[i] < height[j]) lds[i] = max(lds[i], lds[j] + width[i]);
            }
        }

        //找出最大 lis, lds
        int ans_lis = 0, ans_lds = 0;
        for(int i = 0; i < n; i++){
            ans_lis = max(ans_lis, lis[i]);
            ans_lds = max(ans_lds, lds[i]);
        }

        //題目要求，當 LIS 大時有其輸出格式、LDS 也是
        if(ans_lis >= ans_lds)
            cout << "Case " << ++kase << ". Increasing (" << ans_lis << "). Decreasing (" << ans_lds << ").\n";
        else
            cout << "Case " << ++kase << ". Decreasing (" << ans_lds << "). Increasing (" << ans_lis << ").\n";
    }
    return 0;
}