题目描述

难度分:$2500$

输入$n(1 \leq n \leq 5 \times 10^5)$，长为$n$的数组$a(1 \leq a[i] \leq n)$，长为$n$的数组 $cost(-10^9 \leq cost[i] \leq 10^9)$。

然后输入$m(1 \leq m \leq n)$和长为$m$的严格递增数组$b(1 \leq b[i] \leq n)$。

定义$record(arr)$是$arr$的一个严格递增子序列，它的构造过程如下：

• 首先初始化子序列为$[arr[0]]$。
• 继续向后遍历，如果$arr[i]$比子序列的最后一个数大，就加到子序列的末尾。

例如$record([3,1,2,7,7,3,6,7,8]) = [3,7,8]$。

你可以删除$a$的一些数，删除$a[i]$的花费是$cost[i]$。

你需要让$record(a)$等于$b$。

如果无法做到，输出NO；否则输出YES和最小花费。

输入样例$1$

11
4 1 3 3 7 8 7 9 10 7 11
3 5 0 -2 5 3 6 7 8 2 4
3
3 7 10

输出样例$1$

YES
20

输入样例$2$

6
2 1 5 3 6 5
3 -9 0 16 22 -14
4
2 3 5 6

输出样例$2$

NO

算法

树状数组优化DP

如果$b$不是$a$的子序列，肯定无解；否则一定是有解的，利用动态规划来求解。

状态定义

$f_{i,j}$表示从$a$的子数组$[1,i]$中选出一个以$a_i$结尾的子序列，且这个子序列能够与$b$的前缀$[1,j]$匹配的情况下，子序列对应$p$的最大权值和。

由于$b$是个严格递增序列，所以当匹配的子序列确定时，$j$也是确定的。因此，可以优化掉状态$f$中的$j$状态，再做个哨兵$a_0=b_0=0$。

状态转移

根据以上的状态定义，有状态转移方程

$f_i=max_{k \in [0,i),a_k=b_{j-1}}(f_k+\Sigma_{t=k+1}^{i-1}p_t)+p_i$

其中$t$还需要满足，$a_t \leq b_{j-1}$，否则$a_i$不能直接接在$a_k$之后。且$p_t \gt 0$，这是一个出于贪心的考虑，为的是让$f_i$尽可能大。

设$g_k=f_k+\Sigma_{t=k+1}^{i-1}p_t$，那么$f_i=max_{k=0}^{i-1}g_k+p_i$。考虑$f_{i+1}$状态的$g_k$变化，此时只是$\Sigma_{t=k+1}^{i-1}p_t$部分多了个$p_i$（$t \in [k+1,i]$）。对于$k \in [0,i)$，如果$p_i \leq 0$，那$g_k$肯定就不变了；否则所有满足$a_k \geq a_i$的$g_k$都会加上$p_i$；而对于$k=i$的$g_k$，后面的求和起点大于终点，和不存在，有$g_k=f_i$成立。

由于求的是一个前缀最值，而不是任意区间的最值，所以不一定要用线段树来实现，可以用$a_k$作为下标开树状数组，下标$v$处的值为$max_{k \in [0,i),a_k=v}g_k$，这样就能$O(log_2n)$进行状态转移计算$f_i$。动态规划完成之后，只是求出了保留下标的最大值$mx$，要删除下标的最小代价应该为$\Sigma_{i=1}^{n}p[i]-mx$。

复杂度分析

时间复杂度

遍历$i \in [1,n]$计算$f[i]$时间复杂度是$O(n)$。单次状态转移需要先对$b$进行二分查找，时间复杂度为$O(log_2m)$，然后操作树状数组进行转移，而树状数组的范围是$O(n)$级别的，因此操作树状数组的时间复杂度为$O(log_2n)$。而$m \leq n$，因此算法总体的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$a$、$b$、$p$数组，额外空间的瓶颈在于树状数组，空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 500010;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m, a[N], b[N], p[N];
LL f[N];

// 注意本题的树状数组充当的是个差分数组，以单点加来实现区间加
struct BIT{
    LL c[N];
    void add(int x, LL v) {
        for(; x <= n; x += lowbit(x)) {
            c[x] += v;
        }
    }

    LL query(int x) { // 单点查询
        LL s = 0;
        for(; x; x -= lowbit(x)) {
            s += c[x];
        }
        return s;
    }

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

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    LL tot = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        tot += p[i];
    }
    scanf("%d", &m);
    for(int i = 1; i<= m; i++) {
        scanf("%d", &b[i]);
    }
    tr.add(1, -INF);
    for(int i = 1; i <= n; ++i) {
        int j = lower_bound(b + 1, b + 1 + m, a[i]) - b;
        if(j <= m && a[i] == b[j]) {
            // a[i]需要保留，状态转移计算f[i]
            if(j == 1) {
                f[i] = p[i];
            }else {
                f[i] = tr.query(b[j - 1]) + p[i];
            }
        }else {
            f[i] = -INF;
        }
        if(p[i] > 0) {
            tr.add(a[i], p[i]);      // 所有a[k]>=a[i]的g[k]要加上p[i]，在差分数组的左端点上加
        }
        // 更新最大值
        LL temp = tr.query(a[i]);
        if(f[i] > temp) {
            // 最大值更大了，更新区间的左右端点
            tr.add(a[i], f[i] - temp);
            tr.add(a[i] + 1, temp - f[i]);
        }
    }
    LL ans = tr.query(b[m]);
    if(ans > -1e15) {
        puts("YES");
        printf("%lld\n", tot - ans);
    } else {
        puts("NO");
    }
    return 0;
}