【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d242
【解題想法】DP, LIS【筆記】
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[600000], num, idx, tmp, n[600000];
vector <int> v;
vector <int> ans;
int main() {
cin >> num;
v.push_back(num);
n[0] = num;
a[0] = 1;
idx++;
while (cin >> num){
n[idx] = num;
if (num > v[v.size()-1]){
v.push_back(num);
a[idx] = v.size();
}
else {
*lower_bound(v.begin(), v.end(), num) = num;
a[idx] = lower_bound(v.begin(), v.end(), num) - v.begin() + 1;
}
idx++;
}
tmp = v.size();
cout << tmp << "\n-\n";
for (int i = idx-1; i >= 0; i--){
if (a[i] == tmp){
ans.push_back(n[i]);
tmp--;
}
}
for (int i = ans.size()-1; i >= 0; i--){
cout << ans[i] << "\n";
}
}
Python code (credit: Amy Chou)
注意:前三筆測資過關,但最後一筆測資 TLE。
# 找出LIS的長度
def LIS():
v[0] = a[0]
ranking[0] = 0
LIS_len = 1
for i in range(1, N):
l = 0
r = LIS_len
# binary search
while l < r:
mid = (l + r) // 2
if v[mid] >= a[i]:
r = mid
else:
l = mid + 1
#找出a[i]的ranking
ranking[i] = l
v[l] = a[i]
if l == LIS_len:
LIS_len += 1
return LIS_len
# main program
a = []
while True:
try:
a.append(int(input()))
except:
break
N = len(a)
ranking = [0] * N
v = [0] * N
length = LIS()
print(f"{length}\n-")
length -= 1
ans = []
for i in range(N-1, -1, -1):
if (ranking[i] == length):
ans.append(a[i])
length -= 1
for i in ans[::-1]:
print(i)