算法
(离散化,树状数组) O(nlogn)
众所周知,与求上升子序列相关的优化一般有两种:
- 单调栈 & 二分优化
- 线段树 | 树状数组 | 平衡树等数据结构优化
这里求的是上升子序列中所有元素的和的最大值,不太好用单调栈+二分,故想到用树状数组。
可能有些人对数据结构优化最长上升子序列不太了解,这里说一下思路。
先考虑暴力DP:设 f[i] 表示在 a1∼ai 中,且以 ai 结尾的所有上升子序列中,元素和的最大值。
有转移方程:
f[i]=ai+max
将序列 a 离散化,考虑优化对 f _ i 的转移。
设 g _ x 表示所有 j < i 且 a _ j = x 的 f _ j 的最大值,那么 \begin {aligned} \max _ {0 \leq j < i, a _ j < a _ i} f[j] \end {aligned} 就等于 \begin {aligned} \max _ {x < a _ i} g _ x \end {aligned},注意到这项是 g 的一个前缀最大值,这恰可以用树状数组动态维护。
具体可见代码。
时间复杂度
离散化 O(n \log n),树状数组 O(n \log n),故总复杂度为 O(n \log n)。
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll; // 本题中 a 的上线是 10 ^ 9,故答案可能会超过 int 的上限
const int N = 100005;
int n, a[N], diff[N], sz; // 离散化
// 树状数组
ll fw[N], res;
inline void add(int x, const ll c) {
for (; x <= sz; x += x & -x) fw[x] = max(fw[x], c);
}
inline ll qry(int x) {
ll res = 0;
for (; x; x &= x - 1) res = max(res, fw[x]);
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
diff[i - 1] = a[i];
}
sort(diff, diff + n);
sz = unique(diff, diff + n) - diff;
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(diff, diff + sz, a[i]) - diff + 1; // 求出离散化之后的值
ll f = diff[a[i] - 1] + qry(a[i] - 1); // 求出 f[i]。
res = max(res, f), add(a[i], f); // 更新答案并将 f[i] 存到树状数组中 a[i] 的位置。
}
printf("%lld\n", res);
return 0;
}
离散化和转移方程那块 解释不够清晰 实在令人费解
偶像
%%%%%%
膜拜plmm!!
太强了