题目链接

题目描述

有一个序列，每个元素有一个颜色 $c_i$ 和权值 $v_i$，你需要从中选出一些元素，不改变相对顺序的组成一个新序列，使得整个序列的总分最高。

新序列的分数是这样计算的：

对于每个你选出的元素：

如果这个元素和新序列中上一个元素颜色相同，就在总分里加上 $v_i \cdot a$，否则加上 $v_i \cdot b$

$n \times q \le 5 \times 10^7$

简要做法

记录下最大值和次大值的颜色，每次转移的时候讨论下即可

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>

#define int long long

const int N = 1e5 + 5;

int n, q;
int v[N], c[N], f[N];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

signed main()
{
    n = read(), q = read();
    for (int i = 1; i <= n; i++)
        v[i] = read();
    for (int i = 1; i <= n; i++)
        c[i] = read();
    for (; q--;)
    {
        memset(f, 0xcf, sizeof f);
        int a = read(), b = read(), fir_col = 0, sec_col = 0, ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int res = std::max(b * v[i], f[c[i]] + a * v[i]);
            if (c[i] != fir_col)
                res = std::max(res, f[fir_col] + b * v[i]);
            else
                res = std::max(res, f[sec_col] + b * v[i]);
            if (res > f[fir_col] and c[i] != fir_col)
                sec_col = fir_col, fir_col = c[i];
            else if (res > f[sec_col] and c[i] != fir_col)
                sec_col = c[i];
            f[c[i]] = std::max(f[c[i]], res);
            ans = std::max(ans, res);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}