題目: UVa - 11456 - Trainsorting
題目說明
d052. 11456 - Trainsorting - 高中生程式解題系統
解題思路
weighs[]
存放依序車廂的重量,n
為車廂的總數量,之後遍歷陣列,核心想法為,由於新進的車廂只能放在頭尾,因此當遍歷到第 i
車廂時,若能找出 i
到 n - 1
的最長嚴格遞增子序列 ( Longest Increasing Subsequence ) 的長度及最長嚴格遞減子序列 ( Longest Decrease Subsequence ),就可以找到第一個車廂放 i
,能組出的最大車廂重量,因為 LDS 遞減,每個位於 LDS 中的車廂都能放到最前面,而 LIS 遞增,每個位於 LIS 中的車廂都能放到最後面。
有了以上想法後,使用 DP 找出 LIS 及 LDS 即可,記得要從後面開始往前做。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include <bits/stdc++.h>
using namespace std;
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
int T; int n; int mx; int weights[2001]; int LIS[2001]; int LDS[2001];
void read() { mx = 0; cin >> n; for (int i = 0; i < n; ++i) cin >> weights[i], LIS[i] = LDS[i] = 1; }
void solve() { for (int i = n - 1; i >= 0; --i) { for (int j = n - 1; j > i; --j) { if (weights[i] > weights[j]) LIS[i] = max(LIS[j] + 1, LIS[i]); if (weights[i] < weights[j]) LDS[i] = max(LDS[j] + 1, LDS[i]); } mx = max(LIS[i] + LDS[i] - 1, mx); }
cout << mx << '\n'; }
int main() { cin >> T; while (T--) { read(); solve(); } }
|
參考資料
【題解】ZeroJudge d052: 11456 - Trainsorting - Yui Huang 演算法學習筆記