題目： 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;

// reference: https://ppt.cc/feem5x

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)
        {
            // 若 j 能接在 i 後面 ( LIS )
            if (weights[i] > weights[j]) LIS[i] = max(LIS[j] + 1, LIS[i]);
            // 若 j 能接在 i 後面 ( LDS )
            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 演算法學習筆記