A16576 | $Delicate Anti-monotonous Operations$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

生活中有许多重复的工作，Iris 不喜欢它们，然而时间不能倒流，我们只好一路向前。 说回正题，Iris 有一个数列 $a$，数列中的每个数都是 $1$ 到 $w$ 之间的正整数（保证 $w\ge 2$。）。 Iris 定义单次操作为：选择数列中相邻且相等的两个数 $a_i$ 和 $a_{i+1}$，将它们变为 $1$ 到 $w$ 之间的任意两个正整数（可以与原来相同），但是由于 Iris 不喜欢相等的数，因此修改后的 $a_i$ 和 $a_{i+1}$ 必须不等（当然，允许因为后续操作导致 $a_i$ 和 $a_{i+1}$ 与先前操作过的数相等，即操作互相独立。每对数，每个数均可操作多次）。 现在，Iris 希望知道整个数列所有数字和的最大值，以及得到这个最大值所需的最少操作次数。 保证对于每组数据所有 $a_i$ 满足 $1\le a_i\le w$， 所有数据 $n$ 的和不超过 $10^6$。

单个测试点有多组数据，将在输入的开头输入 $t$ 表示，$t\le10^5$。

对于每组数据，输出一行两个数，分别为数列中数字和的最大值和达到此值所需最少操作次数。

输入 #1

2
5 8
1 2 3 4 5
7 5
3 1 2 3 4 1 1

输出 #1

15 0
34 6

C++ 编辑器

输入

输出