# 題目: 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/