题目描述

给定一组矢量算子，要求合理部署这些算子到矩阵计算单元和向量计算单元上，以充分利用计算资源，使得整体执行时间最短。整体执行时间定义为矩阵计算单元总执行时间和向量计算单元总执行时间的最大值。

思路(暴力)

数据范围$n<=1e4$考虑暴力,因为向量单元必须连续，所以考虑直接枚举区间,将$(i,j)$这一段区间纳入向量单元其他的纳入矩阵区间，取二者的最大值再与$ans$取$min$即可

题解：

题目要求我们合理分配一组矢量算子，使其分别在矩阵计算单元和向量计算单元上执行，并且使整体的执行时间最短。由于向量计算单元的执行效率较低（矩阵计算单元的六分之一），我们需要找到一种分配方式，使得两个单元中较大的执行时间尽可能小。

题目内容

深度学习算法由一个个计算单元组成，我们称这些计算单元为算子。

对于完成矢量运的算子我们称为矢量算子，在 $NPU$ 中矩阵计算单元和向量计算单元都可以执行矢量算子，他们是独立可并行执行的，但他们的计算效率是6:1，即假设某个失量算子在矩阵计算单元上执行的时间为 $N$ ，则在向量计算单元上执行的时间为 $6N$ 。

给定一组矢量算子，假设他们都可以部署在矩阵计算单元和向量计算单元。为了充分利用计算资源，我们可以合理部署算子的执行单元，让总体的执行时间最短，总的执行时间为 $MAX$ (矩阵计算单元总的执行时间，向量计算单元总的执行时间)。

为了简化计算模型，我们约定:

1.单个算子只能部署在矩阵计算单元或向量计算单元。

2.部署在向量计算单元的算子必须是按照给定顺序连续的。

输入描述

输入格式:

第一行输入算子数 $n$

第二行输入该组算子在矩阵计算单元的执行时间 $nums$

$1<=n<= 10^4$

$1 <=nums[i] <=10^4$

输出描述

该组算子整体的最短执行时间

样例1

输入

9
1 2 3 4 5 6 7 8 9

输出

39

说明

下标 $5$ 的算子在矩阵计算单元的执行时间为 $6$ ，将它部署在向量计算单元，

执行时间变为 $6*6=36$ ，剩下的算子部署在矩阵计算单元，执行时间为 $1+2+3+4+5+7+8+9=39$ 。

总的执行时间为 $39$ ，没有比这执行时间更短的方案了。

样例2

输入

9
3 2 17 8 3 5 4 18 15

输出

66

说明

下标 $3,4$ 的算子在矩阵计算单元的执行时间为 $8,3$ ，将它部署在向量计算单元,

执行时间变为 $8 * 6 + 3 * 6 = 66$ ，剩下的算子部署在矩阵计算单元，执行时间为 $3+2+17+5+4+18+15=64$ ，

总的执行时间为 $66$ ，没有比这执行时间更短的方案了。