d052. 11456 - Trainsorting -- UVa11456 | From: [118.167.70.47] | 發表日期 : 2025-01-24 18:42

1. 構造問題:

   新的火車可以加入到現有車廂的前面或後面，或者拋棄，輸出最長的「依序重量」序列長度。

 

2. 定義狀態:

   LIS(i) = 從「右到左」看，以 index i 為起點的最長遞增子序列長度

   LDS(i) = 從「左到右」看，以 index i 為起點的最長遞減子序列長度

 

3. 求解小規模的簡單問題:

   對於所有 i，初始化 LIS(i) = 1, LDS(i) = 1

 

4. 狀態轉移方程式:

   LIS(i) = max(LIS(i), LIS(j) + 1 | nums[i] > nums[j] && j > i)

   LDS(i) = max(LDS(i), LDS(j) + 1 | nums[i] > nums[j] && j < i)

 

5. 判斷複雜度:

   時間複雜度: O(n^2)

   空間複雜度: O(n)

 

最終結果:

最長火車長度 = max(LIS(i) + LDS(i) - 1) 對於所有(∀) i