# 題目: UVa 1062 – Containers

# 題目說明

船運送貨物到港口，貨物需要依A到Z的順序排序
字母大的貨物在下，且字母大的貨物不能放在比它小的上方
求貨物至少要先堆成幾堆才能達成

---

INPUT:
每筆資料輸入一個字串，代表貨物到港口的順序
當輸入為end時結束程式

---

OUTPUT:
先輸出第幾個case
接著輸出需要的最小stack數

# 解題方法

其實這題就是在求LIS : 最長嚴格遞增子陣列
利用greedy演算法求出LIS

# 參考程式碼

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	string in;
	int count = 1;

	while (cin >> in && in != "end") {

		vector<char> re;
		re.emplace_back(in[0]);

		for (size_t i = 1; i < in.size(); ++i) {
			if (in[i] > re.back()) re.emplace_back(in[i]);
			else *lower_bound(re.begin(), re.end(), in[i]) = in[i];
		}

		cout << "Case " << count++ << ": " << re.size() << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%201062/