# 題目: UVa 11790 - Murcia's Skyline
# 題目說明
有 N
棟建築,每棟建築有 高度h
與 寬度n
你需要依照高度找出從左至右的 longest increasing subsequence
與 longest decreasing subsequence
將這些 subsequence
的 w
加總,各找出某一個序列的最大 w
合,稱為 w(in)
與 w(de)
若 w(in)
比 w(de)
大,則先輸出 longest increasing subsequence
反之則先輸出 longest decreasing subsequence
INPUT:
第一行有一個整數 S
,代表測資數
每筆測資第一行有一個整數 N
,代表建築的數量
接下來有 N
個整數,代表建築的高度
最後有 N
個整數,代表建築的寬度
OUTPUT:
依照大小輸出 Increasing subsequence
的最大 w
合與 decreasing subsequence
最大 w
合
# 解題方法
標準的動態規劃題
採用 DP
時間複雜度為 O(N^2)
的解法
因為要找 LIS
與 LDS
,所以須做 2 次
其餘與上一題 (11456) 大致相同
# 參考程式碼
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int S, N, cases = 0; | |
cin >> S; | |
while (S-- && cin >> N) | |
{ | |
// init | |
vector<int> h(N), w(N); | |
vector<int> lis(N), lds(N); | |
int ans_lis = 0, ans_lds = 0; | |
for (int i = 0; i < N; ++i) cin >> h[i]; | |
for (int i = 0; i < N; ++i) cin >> w[i], lis[i] = lds[i] = w[i]; | |
// find lis and lds | |
for (int i = 0; i < N; ++i) for (int j = 0; j <= i; ++j) | |
{ | |
if (h[i] > h[j]) lis[i] = max(lis[i], lis[j] + w[i]); | |
if (h[i] < h[j]) lds[i] = max(lds[i], lds[j] + w[i]); | |
ans_lis = max(ans_lis, lis[i]); | |
ans_lds = max(ans_lds, lds[i]); | |
} | |
cout << "Case " << ++cases << ". "; | |
if (ans_lis >= ans_lds) cout << "Increasing (" << ans_lis << "). Decreasing (" << ans_lds << ").\n"; | |
else cout << "Decreasing (" << ans_lds << "). Increasing (" << ans_lis << ").\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.pinghenotes.com/UVa-11456-Trainsorting/
https://summon528.github.io/2017/12/05/UVA-11790-Murcia-s-Skyline/