【題解】ZeroJudge d052: 11456 – Trainsorting

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d052
【解題想法】DP, LIS, LDS 【筆記

【方法1】逆轉原測資,加一份複製的原測資,求最大遞減子序列

  • 題目要求把車廂依重量由大到小排列,把最重的車廂擺在火車的前方。
  • 題目說明車廂以事先排定的順序抵達車站。當一節車廂抵達時,可以把它接在列車的前方或後方,或根本不要這節車廂。列車越長越好。
  • 【例子】四節車廂,重量分別為 [3, 1, 4, 2],依序進站。
    • 4 – 3 – 1 或 4 – 3 – 2 都可以是答案。
    • 因為新進的車廂可以接在列車的前方或後方,先把原測資「逆轉」,後面再接續一份「複製的原測資」,變成 [2, 4, 1, 3, 3, 1, 4, 2],再求其最長「遞減」子序列的長度即可。這樣做,一定會有一個合法的起點。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 4005;
int a[maxn];
int LIS[maxn];

int main() {
    int TC, N, A;
    int maxi;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> TC;
    while (TC--){
        cin >> N;
        memset(a, 0, sizeof(a));
        memset(LIS, 0, sizeof(LIS));
        for (int i=0; i<N; i++){
            cin >> A;
            a[N-1-i] = A;
            a[N+i] = A;
        }
        LIS[0] = 1;
        for (int i=1; i<2*N; i++){
            maxi = 0;
            for (int j=0; j<i; j++){
                if (a[j] < a[i])
                    maxi = max(maxi, LIS[j]);
            }
            LIS[i] = maxi + 1;
        }
        maxi = 0;
        for (int i=1; i<2*N; i++){
            maxi = max(maxi, LIS[i]);
        }
        cout << maxi << "\n";
    }
    return 0;
}

【方法2】從後往前,同時計算 LIS 及 LDS

  • 使用Python時,依照上述的做法會 TLE
  • 改成從後往前,計算最大上升子序列(LIS),及計算最大下降子序列(LDS)。
  • LIS[i]:從第 i 節車廂開始拿,上升的 LIS[i] – 1節車廂,逐一接到第 i 節車廂的前面。
  • LDS[i]:從第 i 節車廂開始拿,下降的 LDS[i] – 1節車廂,逐一接到第 i 節車廂的後面。
  • LIS[i] + LDS[i] – 1:即為可接起來的最大車廂長度。

C++ code (credit: Yui Huang)

#include <iostream>
#include <cstring>
using namespace std;

int t, n, a[2005], LIS[2005], LDS[2005], ans;

int main(){
    while (cin >> t){
        while (t--){
            cin >> n;
            if (n == 0){
                cout << 0 << "\n";
                continue;
            }
            for (int i = 0; i < n; i++){
                cin >> a[i];
            }
            ans = 0;
            for (int i = n-1; i >= 0; i--){
                LIS[i] = 1;
                LDS[i] = 1;
                for (int j = n-1; j > i; j--){
                    if (a[i] > a[j]) LIS[i] = max(LIS[i], LIS[j] + 1);
                    if (a[i] < a[j]) LDS[i] = max(LDS[i], LDS[j] + 1);
                }
                ans = max(ans, LIS[i] + LDS[i] - 1);
            }
            cout << ans << "\n";
        }
    }
}

Python Code (credit: Amy Chou)

T = int(input())
for iter1 in range(T):
    n = int(input())
    if (n == 0):
        print(0)
        continue

    a = [None] * n
    for i in range(n):
        a[i] = int(input())

    LIS = [None] * n
    LDS = [None] * n
    ans = 0
    for i in range(n-1, -1, -1):
        LIS[i] = 1 #從後向前,計算最大上升子序列
        LDS[i] = 1 #從後向前,計算最大下降子序列
        for j in range(n-1, i, -1):
            if (a[i] > a[j]) and (LIS[i] <= LIS[j]):
                LIS[i] = LIS[j] + 1;
            if (a[i] < a[j]) and (LDS[i] <= LDS[j]):
                LDS[i] = LDS[j] + 1

        if (ans < LIS[i] + LDS[i] - 1):
            ans = LIS[i] + LDS[i] - 1

    print(ans)
分享本文 Share with friends