思路:枚举+前缀和

题目要求把数组分成左右两个部分，价值为左右价值之和的乘积，自然的能想到用两个前缀和维护.$\\$$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() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
    cin >> n;
	vector<int> v(n + 1);
	vector<int>pre(n + 2, 0);
	vector<int>suf(n + 2, 0);
	for (int i = 1; i <= n; i++)
		cin >> v[i];
	for (int i = 1; i <= n; i++)
		pre[i] = pre[i - 1] + v[i];
	for (int i = n; i >= 1; i--)
		suf[i] = suf[i + 1] + v[i];
	long long ans = 2e18;
	for (int i = 1; i <= n-1; i++)
		ans = min(ans, 1ll*pre[i] * suf[i + 1]);
	cout << ans << '\n';
	return 0;
}

$python$

from typing import List

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    v = list(map(int, data[1:n+1]))
    pre = [0] * (n + 2)
    suf = [0] * (n + 2)
    
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] + v[i - 1]
    
    for i in range(n, 0, -1):
        suf[i] = suf[i + 1] + v[i - 1]
    
    ans = float('inf')
    for i in range(1, n):
        ans = min(ans, pre[i] * suf[i + 1])
    
    print(ans)

if __name__ == "__main__":
    main()

$java$

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] v = new int[n + 1];
        int[] pre = new int[n + 2];
        int[] suf = new int[n + 2];

        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + v[i];
        }

        for (int i = n; i >= 1; i--) {
            suf[i] = suf[i + 1] + v[i];
        }

        long ans = Long.MAX_VALUE;
        for (int i = 1; i <= n - 1; i++) {
            ans = Math.min(ans, (long) pre[i] * suf[i + 1]);
        }

        System.out.println(ans);
    }
}

题目内容

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

这条项链由$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