Choosing Balls

题目描述

There are $n$ balls. They are arranged in a row. Each ball has a color (for convenience an integer) and an integer value. The color of the $i$-th ball is $c_i$ and the value of the $i$-th ball is $v_i$.

Squirrel Liss chooses some balls and makes a new sequence without changing the relative order of the balls. She wants to maximize the value of this sequence.

The value of the sequence is defined as the sum of following values for each ball (where $a$ and $b$ are given constants):

• If the ball is not in the beginning of the sequence and the color of the ball is same as previous ball’s color, add $\text{the value of the ball} \times a$.
• Otherwise, add $\text{the value of the ball} \times b$.

You are given $q$ queries. Each query contains two integers $a_i$ and $b_i$. For each query find the maximal value of the sequence she can make when $a=a_i$ and $b=b_i$.

Note that the new sequence can be empty, and the value of an empty sequence is defined as zero.

题意概述

$n$个球排成一行，第$i$个球的颜色是$c_i$，价值是$v_i$。一个序列的价值等于与前一个球颜色相同的球的价值之和乘以$a$加其他球的价值之和乘以$b$。空序列的价值为$0$。有$q$组询问，每组询问给定$a, b$，求这$n$个球的最大价值子序列。

数据范围：$1 \le c_i \le n \le 10^5, \ 1 \le q \le 500, \ 0 \le |v_i|, |a|, |b| \le 10^5$。

算法分析

令$f_i$表示以第$i$种颜色结尾的序列的最大价值。设当前处理到第$i$个球，转移方程如下

$$
f_{c_i}=\max(\max(f_x \mid x \neq c_i, 0)+v_i \times b, f_{c_i}+v_i \times a)
$$

转移时维护当前$f_i$的最大值和次大值，这样可以直接得到$\max(f_x \mid x \neq c_i)$。

代码

import std.stdio;

static immutable MAX_NUM = 1000000000000000;

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

int main() {
  auto input = stdin;
  auto output = stdout;
  input.readf(" %d %d", &n, &q);
  v.length = c.length = f.length = n + 1;
  for (int i = 1; i <= n; ++ i) input.readf(" %d", &v[i]);
  for (int i = 1; i <= n; ++ i) input.readf(" %d", &c[i]);
  while (q --) {
    long a, b, max = -MAX_NUM, sec = -MAX_NUM, ans = 0;
    input.readf(" %d %d", &a, &b);
    for (int i = 1; i <= n; ++ i) f[i] = -MAX_NUM;
    for (int i = 1; i <= n; ++ i) {
      long p = f[c[i]] == max ? sec : max, q = f[c[i]];
      bool flag = f[c[i]] == max;
      if (f[c[i]] < v[i] * b) f[c[i]] = v[i] * b;
      if (f[c[i]] < p + v[i] * b) f[c[i]] = p + v[i] * b;
      if (f[c[i]] < q + v[i] * a) f[c[i]] = q + v[i] * a;
      if (f[c[i]] >= max) {
        if (! flag) sec = max;
        max = f[c[i]];
      } else if (f[c[i]] > sec) sec = f[c[i]];
    }
    for (int i = 1; i <= n; ++ i) {
      if (ans < f[i]) ans = f[i];
    }
    output.writeln(ans);
  }
  return 0;
}