1 条题解

  • 0
    @ 2026-11-12 21:57:53

    [Q] Flowers(dp_q)题解

    题意简述

    NN 朵花,高度 hih_i 两两不同、美丽值 aia_i。删去一些花使剩下的高度从左到右递增,求剩下花美丽值之和的最大值。

    思路

    状态

    本质上是"带权的最长上升子序列"。设 fif_i = 以第 ii 朵花结尾(保留它)时能获得的最大美丽值之和:

    $$f_i = a_i + \max\{\, f_j : j < i,\; h_j < h_i \,\}.$$

    答案 max⁡ifi\max_i f_i。

    优化

    朴素转移 O(N2)O(N^2) 会超时。需要快速求"前缀(h<hih < h_i)最大值",且必须按原顺序插入(因为 j<ij < i 的限制)。

    用树状数组维护下标为高度的前缀最大值:

    • 查:query(h_i - 1);
    • 更新:update(h_i, f_i)(取 max 而非相加)。

    hi≤Nh_i \le N 且两两不同,直接以 hih_i 作为下标,无需离散化。

    为什么 j<ij<i 必须满足

    如果只要求 hj<hih_j < h_i 而不要求位置在前,就变成"按高度排序后求最大权递增序列",会选出位置颠倒的组合(如 h=[3,1,4,2]h = [3,1,4,2],a=[10,20,30,40]a=[10,20,30,40] 时错解会取 1,2,3,41,2,3,4 得 100100,而正确答案是 6060)。

    复杂度

    时间 O(Nlog⁡N)O(N\log N),空间 O(N)O(N)。

    参考代码

    #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;
    }
    

    易错点

    1. 输入是两行数组(先 NN 个高度、再 NN 个美丽值),不是 NN 行数对。
    2. 树状数组要维护 max,不是 sum。
    3. 答案可达 2×10142\times10^{14},必须 long long(样例 3 就是 5×1095\times10^9)。
    4. 不要按高度排序后再做——那会丢掉位置约束。

    数据说明

    共 16 组:4 组官方样例;N=1/2/3/5/10/100/1000N=1/2/3/5/10/100/1000 随机排列;N=2×105N=2\times10^5 的升序(答案全取)、降序(只能取一朵)、随机排列三组。

    • 1

    信息

    ID
    26
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    1
    已通过
    1
    上传者