【題目敘述】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)