# 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$个球的最大价值子序列。

## 算法分析

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

## 代码

import std.stdio;

static immutable MAX_NUM = 1000000000000000;

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

int main() {
auto input = stdin;
auto output = stdout;
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;
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;
} 418 I'm a teapot