# 題目: UVa 11456 - Trainsorting

# 題目說明

一節車廂可以選擇放在火車頭或火車尾
車廂必須按照重量由重到輕從火車頭開始排列
你需要找到最多能連接幾節車廂

---

INPUT:
第一行有一個整數S，代表測資數
每筆測資第一行有一個整數N，代表車廂數
接下來N行，每行有一個整數，代表車廂的重量

---

OUTPUT:
輸出最多能連接幾節車廂

# 解題方法

這是Longest Increasing Subsequence (最長遞增子序列)的問題
由於車廂可以排在前後，所以我們將輸入的資料複製一份顛倒放在前面

例如:

接著透過dp找到最長遞增子序列

# 參考程式碼

#include <iostream>
#include <vector>

using namespace std;

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

	int S, N, a, ans;
	vector<int> train;
	vector<int> len;

	cin >> S;

	while (S-- && cin >> N)
	{
		train.assign(N * 2, 0);
		len.assign(N * 2, 1);
		ans = 0;

		for (int i = 0; i < N; ++i)
		{
			cin >> a;
			train[N + i] = train[N - i - 1] = a;
		}
	
		for (int i = 0; i < N * 2; ++i) for (int j = 0; j < i; ++j)
		{
			if (train[i] > train[j]) len[i] = max(len[i], len[j] + 1);
			ans = max(ans, len[i]);
		}

		cout << ans << "\n";
	}

	return 0;
}

# 參考資料

https://ithelp.ithome.com.tw/articles/10253577
https://www.youtube.com/watch?v=fV-TF4OvZpk
http://naivered.github.io/2018/03/04/Problem_Solving/UVa/UVa-11456-Trainsorting/