# 題目: UVa 11790 - Murcia's Skyline

# 題目說明

N 棟建築,每棟建築有 高度h寬度n
你需要依照高度找出從左至右的 longest increasing subsequencelongest decreasing subsequence
將這些 subsequencew 加總,各找出某一個序列的最大 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) 的解法
因為要找 LISLDS ,所以須做 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/