思路:枚举+前缀和

题目要求把数组分成左右两个部分，价值为左右价值之和的乘积，自然的能想到用两个前缀和维护.$\\$$pre_i$表示前i颗珍珠价值之和.$\\$$suf_i$表示$a_i$至$a_n$的珍珠价值之和.$\\$处理完成之后枚举$1$至$n-1$,取$min$($pre_i$$*$$suf_{i+1}$)即可 $\\$ 时间复杂度$o(n)$

代码如下

$cpp$

#include <bits/stdc++.h>
using namespace std;
int main() {

题目内容

小红是一位珠宝设计师，他最近设计了一条独特的珍珠项链。

这条项链由$n$颗珍珠组成，每颗珍珠都有其独特的价值。

小红想要将这条项链切割成两部分，以制作成一对手链。

为了使这对手链看起来协调，小红决定将项链切割成两部分，使得左边部分珍珠的总价值乘以右边部分珍珠的总价值最小。

他希望你能帮他计算出这个最小值。

输入描述

第一行输入一个整数$n$，表示珍珠项链的长度。

第二行输入$n$个整数$a_1,a_2,…, a_n$，表示每颗珍珠的价值。

输出描述

输出一个整数，表示切割后两部分珍珠总价值的乘积的最小值。

样例1

输入

5
1 2 3 4 5

输出

14

说明

将项链在第一颗珍珠后切割,左边部分价值为$1$，右边部分价值为$14(2+3+4+5=14)$，

乘积为14，这是最小的可能值。

• $2≤n≤10^6$
• $-10^3 ≤a_i≤ 10^3$

样例2

输入

2 1 3 4

输出

16