1 条题解
-
0
[Q] Flowers(dp_q)题解
题意简述
朵花,高度 两两不同、美丽值 。删去一些花使剩下的高度从左到右递增,求剩下花美丽值之和的最大值。
思路
状态
本质上是"带权的最长上升子序列"。设 = 以第 朵花结尾(保留它)时能获得的最大美丽值之和:
$$f_i = a_i + \max\{\, f_j : j < i,\; h_j < h_i \,\}.$$答案 。
优化
朴素转移 会超时。需要快速求"前缀()最大值",且必须按原顺序插入(因为 的限制)。
用树状数组维护下标为高度的前缀最大值:
- 查:
query(h_i - 1); - 更新:
update(h_i, f_i)(取 max 而非相加)。
且两两不同,直接以 作为下标,无需离散化。
为什么 必须满足
如果只要求 而不要求位置在前,就变成"按高度排序后求最大权递增序列",会选出位置颠倒的组合(如 , 时错解会取 得 ,而正确答案是 )。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <algorithm> using namespace std; long long bit[200005]; void upd(int i, long long v, int n) { for (; i <= n; i += i & (-i)) bit[i] = max(bit[i], v); } long long qry(int i) { long long r = 0; for (; i > 0; i -= i & (-i)) r = max(r, bit[i]); return r; } int main() { int n; scanf("%d", &n); static int h[200005]; static long long a[200005]; for (int i = 1; i <= n; i++) scanf("%d", &h[i]); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); long long ans = 0; for (int i = 1; i <= n; i++) { long long v = qry(h[i] - 1) + a[i]; upd(h[i], v, n); ans = max(ans, v); } printf("%lld\n", ans); return 0; }易错点
- 输入是两行数组(先 个高度、再 个美丽值),不是 行数对。
- 树状数组要维护 max,不是 sum。
- 答案可达 ,必须
long long(样例 3 就是 )。 - 不要按高度排序后再做——那会丢掉位置约束。
数据说明
共 16 组:4 组官方样例; 随机排列; 的升序(答案全取)、降序(只能取一朵)、随机排列三组。
- 查:
- 1
信息
- ID
- 26
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者