一、命名规则
\(LIS\):最长上升子序列
\(LDS\):最长下降子序列
二、\(LIS\)的贪心+二分求法 [这个不是重点，就参考对照一下]
f[0] = a[0];
for (int i = 1; i < n; i++) {
if (a[i] > f[fl])
f[++fl] = a[i];
else
*lower_bound(f, f + fl, a[i]) = a[i];
}
printf("%d\n", fl + 1);
三、直面\(LDS\)
g[0] = a[0];
for (int i = 1; i < n; i++) {
if (a[i] <= g[gl])
g[++gl] = a[i];
else
*upper_bound(g, g + gl, a[i], greater
}
printf("%d\n", gl + 1);
四、加负号转为\(LIS\)
//最长上升子序列的所有元素全加上负号不就变成最长下降子序列(LDS)
memcpy(b, a, sizeof a);
for (int i = 0; i < n; i++) b[i] = -b[i];
g[0] = b[0];
for (int i = 1; i < n; i++) {
if (b[i] >= g[gl])
g[++gl] = b[i];
else
*upper_bound(g, g + gl, b[i]) = b[i];
}
printf("%d\n", gl + 1);
五、数组翻转转为\(LIS\)
//将原数组拷贝出来，翻转，再求LIS就是原数组的LDS
memcpy(b, a, sizeof a);
reverse(b, b + n);
g[0] = b[0];
for (int i = 1; i < n; i++) {
if (b[i] >= g[gl])
g[++gl] = b[i];
else
*upper_bound(g, g + gl, b[i]) = b[i];
}
printf("%d\n", gl + 1);
六、完整代码
#include
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int f[N], fl, g[N], gl;
int n;
// LIS:最长上升子序列
// LDS:最长下降子序列
/*
测试数据1
7
3 1 2 1 8 5 6
答案：3 3 3
测试数据2
8
1 2 2 3 4 3 1 0
答案：4 4 4
*/
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//最长上升子序列
// f[0] = a[0];
// for (int i = 1; i < n; i++) {
// if (a[i] > f[fl])
// f[++fl] = a[i];
// else
// *lower_bound(f, f + fl, a[i]) = a[i];
// }
// printf("%d\n", fl + 1);
//****************************************************************************************************************//
//最长下降子序列:方法1
//将原数组拷贝出来，翻转，再求LIS就是原数组的LDS
memset(g, 0, sizeof g);
gl = 0;
memcpy(b, a, sizeof a);
reverse(b, b + n);
g[0] = b[0];
for (int i = 1; i < n; i++) {
if (b[i] >= g[gl])
g[++gl] = b[i];
else
*upper_bound(g, g + gl, b[i]) = b[i];
}
printf("%d\n", gl + 1);
//最长下降子序列:方法2
//最长上升子序列的所有元素全加上负号不就变成最长下降子序列(LDS)
memset(g, 0, sizeof g);
gl = 0;
memcpy(b, a, sizeof a);
for (int i = 0; i < n; i++) b[i] = -b[i];
g[0] = b[0];
for (int i = 1; i < n; i++) {
if (b[i] >= g[gl])
g[++gl] = b[i];
else
*upper_bound(g, g + gl, b[i]) = b[i];
}
printf("%d\n", gl + 1);
// 最长下降子序列:方法3
// 既不改负号，也不翻转，而是正常顺序枚举，如果当前元素小于等于栈顶元素，那么接在栈顶元素后面，否则通过二分找到第一个小于当前元素的栈内元素并替换
memset(g, 0, sizeof g);
gl = 0;
g[0] = a[0];
for (int i = 1; i < n; i++) {
if (a[i] <= g[gl])
g[++gl] = a[i];
else
*upper_bound(g, g + gl, a[i], greater
}
printf("%d\n", gl + 1);
return 0;
}