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_{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];
  return 0;

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *