AcWing第3场周赛 — C.最大上升子序列和

2021-11-23 · 57次阅读 · 原创 · 数据结构与算法

#题解 #动态规划 #离散化 #树状数组

题目链接

题面

给定一个长度为 n 的整数序列 a1,a2,…,an。

请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。

请问这个最大值是多少？

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出最大的上升子序列和。

数据范围

对于前三个测试点，1≤n≤4。
对于全部测试点，1≤n≤10⁵,1≤ai≤10⁹。

输入样例1：

2
100 40

输出样例1：

输入样例2：

4
1 9 7 10

输出样例2：

样例解释

对于样例 1，我们只选取 100。

对于样例 2，我们选取 1,9,10。

题解

离散化、动态规划、树状数组

对于本题，首先想到的便是动态规划去求解，用飞f[i] 代表以第 i 个数字结尾的最长上升子序和，则遍历 a[i] 的时候，每次需要在区间 [1, i-1] 中找到小于 a[i] 的下标 j , 对于再在这些多个 j 中找到最大的 f[j] 来更新 f[i]，即状态转移方程为：

$f[i] = max(a[i], \max_{1 \le j <i - 1, a[j] < a[i]}(f[j] + a[i]))$

则如果使用暴力 dp，其复杂度为 $O(n^2)$ ，而数据范围 n 最大能取到 10⁵，则该算法会TLE。接下来考虑对其进行优化。

观察状态转移方程可以发现，每次内层循环是找前 i-1 个数中比 a[i] 小，但以其为结尾的最长上升子序和 f[j] 最大的数。

我们可以将这 n 个数作为下标，其对应的值为 f[i] 构造一个新的数组 $g[a[i]] = f[i]$ ，然后生成其前缀最大值 $s[a[i]] = \max_{1 \le j < a[i]}(f[j])$ 则每遍历到一个数 a[i]，g 数组的前缀最大值 s[a[i] - 1] 即为其 f[i] 对应的更新值。

然后看数据范围，发现 a[i] 较大，然而实际最多只有 10⁵ 个不同的数，则需要离散化，将 a[i] 从范围 [1, 10⁹] 压缩到 [1, 10⁵]，作为下标，则使用树状数组来维护前缀最大值即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
typedef long long LL;
int n, a[N];
LL f[N], tr[N];
vector<int> nums;

//树状数组下标从1开始
int get(int x){
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
}

int lowbit(int x){
    return x & -x;
}

void add(int x, LL v){
    for(; x <= n; x += lowbit(x)) tr[x] = max(tr[x], v);
}

LL query(int x){
    LL ans = 0;
    for(; x; x -= lowbit(x)) ans = max(ans, tr[x]);
    return ans;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }
    
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    LL ans = 0;
    for(int i = 1; i <= n; i++){
        int k = get(a[i]);
        f[i] = query(k - 1) + a[i];
        ans = max(ans, f[i]);
        add(k, f[i]);
    }
    printf("%lld\n", ans);
    
    return 0;
}

标题：	AcWing第3场周赛 — C.最大上升子序列和
链接：	https://www.fightingok.cn/detail/147
更新：	2022-09-18 22:42:57
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可