题目描述

难度分:$2000$

输入$n(1 \leq n \leq 10^5)$，$q(1 \leq q \leq 500)$和长为$n$的数组$v(-10^5 \leq v[i] \leq 10^5)$，长为$n$的数组$c(1 \leq c[i] \leq n)$。

有$n$个球排成一排，第$i$个球的价值为$v[i]$，颜色为$c[i]$。

然后输入$q$个询问，每个询问输入$a$和$b$，范围$[-10^5,10^5]$。对每个询问，计算：

从这一排球中，选出一个子序列，子序列的价值和为：

• 如果球不在序列开头，且球的颜色与前一个球的颜色相同，则加上球的值$\times a$。
• 否则，加上球的值$\times b$。

输出子序列的价值和的最大值。子序列可以是空的，此时价值和为 0。

注：子序列不一定连续。

输入样例$1$

6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0

输出样例$1$

20
9
4

输入样例$2$

4 1
-3 6 -1 2
1 2 3 1
1 -1

输出样例$2$

5

算法

动态规划

想了好久贪心没想出来怎么贪，所以感觉还是只能DP。

状态定义

$f[i][c]$表示遍历到$i$位置，前一个颜色为$c$，考虑$[i,n]$中选球能够得到的最大价值。可以发现这样开空间的话，$i \in [1,n]$，$c \in [1,n]$直接就MLE了。考虑到我们DP是从前往后DP，当遍历到$i$位置时前面的信息已经有了，所以第一维$i$可以优化掉。

状态转移

当前可以选择$c_i$这个颜色的球，如果前面一个球的颜色不是$c_i$，假设为$c_p$（前面没有球就看做$c_p=0$，初始化$f[0]=0$，其他颜色的DP值都是负无穷），则有状态转移方程$f[c_i]=max_{c_p \neq c_i}f[c_p]+b \times v_i$。

如果前一个球颜色就是$c_i$，则有状态转移方程$f[c_i]=f[c_i]+max(0,a \times v_i)$。

维护$top_2$最值的优化

这个套路$ABC$也出过，一定要学会！

此时发现是动态求区间最大值的操作，想用线段树来存$f$数组，但是很遗憾，这个数据量下加个$log$会TLE，所以还是得优化成线性的时间复杂度。发现转移后$f$数组中的值是单调不减的，我们只需要保存前面最大值的颜色和次大值的颜色，就可以在$O(1)$的时间复杂度下完成状态转移。

复杂度分析

时间复杂度

状态数量为$O(n)$，单次转移的时间复杂度为$O(1)$，因此每次动态规划的时间复杂度为$O(n)$，$q$次询问的总时间复杂度为$O(nq)$。

空间复杂度

除了输入的$v$数组和$c$数组，空间消耗只有DP数组$f$，它的大小只和颜色数量$n$有关，是线性的，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, q, v[N], c[N];
LL f[N];

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    while(q--) {
        LL a, b;
        scanf("%lld%lld", &a, &b);
        for(int i = 1; i <= n; i++) {
            f[i] = -INF;
        }
        LL ans = 0;
        int pre = 0, prepre = 0;
        for(int i = 1; i <= n; i++) {
            LL res = max(b*v[i], f[c[i]] + a*v[i]);
            if(c[i] != pre) {
                res = max(res, f[pre] + b*v[i]);
            }else {
                res = max(res, f[prepre] + b*v[i]);
            }
            if(res > f[pre]) {
                if(pre != c[i]) {
                    prepre = pre;
                    pre = c[i];
                }else {
                    pre = c[i];
                }
            }else { 
                if(res > f[prepre] && c[i] != pre) {
                    prepre = c[i];
                }
            }
            f[c[i]] = max(f[c[i]], res);
            ans = max(ans, res);
        }
        printf("%lld\n", ans);
    }
    return 0;
}