CF2167G 题解

传送门：洛谷 CF2167G Mukhammadali and the Smooth Array | Codeforces G. Mukhammadali and the Smooth Array

更佳的阅读体验：CF2167G 题解

在阅读本题解之前，请确保你已经对最长不降子序列（Longest Non-decrease Subsequence）模型有所了解。

简要题意：给你一个序列

a

，你可以进行任意次操作，花费

c_i

的代价将

a_i

替换为任意整数，求将

a

变得单调不降的最小代价。

考虑这样一个事实：如果不作修改的点本身是单调不降的，那么就一定有修改方案使得整个序列单调不降。

我们希望总代价尽可能小，也就是保留的点的代价之和尽可能大，因此我们实际上想找的是一个单调不降的子序列，使得这个子序列的权值之和最大。此时，我们发现这实际上是一个带权最长不降子序列问题，直接套板子即可。

n \le 8000

，那么

O(n^2)

的暴力 DP 就足以通过，不需要任何优化。

CPP

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 8010;
int t, n, a[N];
ll c[N], f[N], sum;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        sum = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> c[i], sum += c[i];
        for (int i = 1; i <= n; ++i) {
            f[i] = c[i];
            for (int j = 1; j < i; ++j)
                if (a[j] <= a[i]) f[i] = max(f[i], f[j] + c[i]);
        } cout << sum - *max_element(f + 1, f + n + 1) << '\n';
    } return 0;
}

到这里，你已经可以通过本题。但如果你还有兴趣了解进一步的优化，欢迎继续阅读。

O(n^2)

的复杂度只能勉强通过

n \le 8000

的数据，那么如果

n \le 10^5

呢？我们很自然地想到了非带权的最长不降子序列问题的单调栈优化。

那么，这样的优化能否用在带权的问题上呢？

答案是否定的。

回顾朴素问题的单调栈优化。我们维护了一个尾部数组

t

，

t_{len}

表示长度为

len

的不降子序列中，末尾元素的最小值。当我们枚举到一个新的数

a_i

时，我们通过二分找到

a_i

应该放入的位置，并更新对应的元素。

这种贪心的正确性在于，对于同样长度的子序列，如果末尾的数更小，那么一定不会比末尾的数更大的方案更劣，因为末尾更小的子序列更有可能在接下来的枚举中被延长。

然而在本题中，我们要求的并不是最大的长度，而是最大的保留元素的权值和。这样，“末尾更小一定更优”的思想就不一定正确了。

观察上面那份代码的 DP 过程，我们实际上可以写出下面的转移方程：

f_i = c_i + \max \limits_{j < i, a_j \le a_i} f_j \nonumber

观察这个“前缀最大值”的形式，我们立刻想到可以使用一个类似权值树状数组的数据结构，来维护值域上的

f

的最大值。

由于

a_i

的数据范围比较大，我们还需要对

a

做一次离散化。

时间复杂度

O(n \log n)

。

CPP

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 8010;
int t, n, a[N], d[N];
ll c[N], sum, ans;
struct BIT {
    ll maxn[N];
    void clear() {
        for (int i = 1; i <= n; ++i) maxn[i] = 0;
    } void update(int k, ll x) {
        for (; k <= n; k += k & -k) maxn[k] = max(maxn[k], x);
    } ll query(int k) {
        ll res = 0;
        for (; k; k -= k & -k) res = max(res, maxn[k]);
        return res;
    }
} bit;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        ans = sum = 0;
        bit.clear();
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> c[i], sum += c[i];
        copy(a + 1, a + n + 1, d + 1);
        sort(d + 1, d + n + 1);
        int tot = unique(d + 1, d + n + 1) - d - 1;
        for (int i = 1; i <= n; ++i)
            a[i] = lower_bound(d + 1, d + tot + 1, a[i]) - d;
        for (int i = 1; i <= n; ++i) {
            ll cur = bit.query(a[i]) + c[i];
            ans = max(ans, cur);
            bit.update(a[i], cur);
        } cout << sum - ans << '\n';
    } return 0;
}

至此，恭喜你已经学会了最长不降子序列问题的树状数组优化！

文章操作

相关推荐

评论

CF2167G 题解