首页 > 试题广场 >

支配权值划分

[编程题]支配权值划分
  • 热度指数：268 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个数组 t，定义任意数 x 在 t 中的出现次数为 \mathrm{cnt}(x)。称 t 被 v 支配，当且仅当对任意 v' 有 \mathrm{cnt}(v)\ge \mathrm{cnt}(v')；若出现次数相同，则取数值最大的那个v。定义数组 t 的权值为 v \times |t|（其中 |t| 为 t 的长度）。
\hspace{15pt}现在给定一个长度为 n 的数组 a_1,a_2,\dots,a_n，你需要将其划分为若干个非空连续子数组，使得各子数组权值之和最小，输出该最小值。

\hspace{15pt}【子数组】子数组为原数组中任意一个连续且非空的元素区间。


输入描述:
\hspace{15pt}输入包含多组测试数据。第一行包含整数 T\left(1\leqq T\leqq 10^3\right) 表示测试组数。每组数据描述如下： 
\hspace{30pt}第一行包含一个整数 n\ \left(1\leqq n\leqq 2\times 10^3\right)； 
\hspace{30pt}第二行包含 n 个整数，表示数组 a_1,a_2,\dots,a_n\ \left(-10^9\leqq a_i\leqq 10^9\right)。 
\hspace{15pt}保证所有测试中 n 的总和不超过 5\times 10^3。


输出描述:
\hspace{15pt}对于每组测试数据，输出一行一个整数，表示将数组划分为若干非空连续子数组后，权值之和的最小值。
示例1

输入

3
5
1 1 2 2 3
3
5 5 5
4
1 2 3 4

输出

8
15
10

说明

\hspace{15pt}样例一：一种最优划分为 [1,1,2],[2],[3]，权值分别为 1\times3, 2\times1, 3\times1，总和 3+2+3=8。 
\hspace{15pt}样例二：任意划分总和均为 5\times3=15。 
\hspace{15pt}样例三：将其划分为单点 [1],[2],[3],[4]，总和 1+2+3+4=10。
算法知识视频讲解
开通博客

暂无题解

问题信息

难度：
1条回答 102浏览

热门推荐

相关试题

支配权值划分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号