AcWing 1017. 怪盗基德的滑翔翼【二分法和dp做法】
原题链接
简单
朴素dp
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int k, n, a[N];
int f1[N], f2[N];
int main() {
cin >> k;
while(k--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
fill(f1 + 1, f1 + n + 1, 1);
fill(f2 + 1, f2 + n + 1, 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j < i; j++) {
if(a[i] > a[j]) {
f1[i] = max(f1[i], f1[j] + 1);
}
}
}
for(int i = n; i >= 1; i--) {
for(int j = n; j > i; j--) {
if(a[i] > a[j]) {
f2[i] = max(f2[i], f2[j] + 1);
}
}
}
int res = 0;
for(int i = 1; i <= n; i++) {
res = max(res, f1[i]);
res = max(res, f2[i]);
}
cout << res << endl;
}
}
二分
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int k, n, a[N];
int f[N], g[N];
int main() {
cin >> k;
while(k--) {
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
//二分法求最长上升子序列
int s = 0;
for(int i = 0; i < n; i++) {
if(s == 0 || f[s - 1] < a[i]) {
f[s++] = a[i];
}
else{
int l = 0, r = s - 1;
while(l < r) {
int mid = l + r >> 1;
if(a[i] <= f[mid]) r = mid;
else l = mid + 1;
}
f[l] = a[i];
}
}
//二分法求最长下降子序列
int t = 0;
for(int i = 0; i < n; i++) {
if(t == 0 || a[i] < g[t - 1]) {
g[t++] = a[i];
}
else{
int l = 0, r = t - 1;
while(l < r) {
int mid = l + r >> 1;
if(a[i] >= g[mid]) r = mid;
else l = mid + 1;
}
g[l] = a[i];
}
}
cout << max(s, t) << endl;
}
return 0;
}