首页 > 试题广场 >

牛牛与切割机

[编程题]牛牛与切割机

热度指数：3154 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个序列 $a_1, a_2, ..., a_n$ ，牛牛将对这个序列切割一刀（划分分成两个不相交的非空序列，一个序列为 $a_1, \dots, a_p$ ，另一个序列为 $a_{p+1}, \dots, a_n$ ），牛牛切割的代价为两个序列元素和的乘积。牛牛想知道切割代价最小是多少。

输入描述:

第一行输入一个整数 ，表示序列的长度 。
第二行输入  个整数 ，表示序列的元素 。

输出描述:

输出一个整数表示切割代价最小是多少。

示例1

输入

5
1 2 3 4 5

输出

说明

序列被划分为1 和 2 3 4 5，右边和为 14。

示例2

输入

4
2 1 3 4

输出

说明

序列被划分为 2 和 1 3 4。

算法知识视频讲解

BraveCoder

发表于 2025-09-09 10:28:32

设做序列和为x，总序列和为常数k，则右序列和为k-x；即问题可等价为：求y=x(k-x)=-x^2+xk的最小值，抛物线开口向下，则其最小值必在两个端点处取得。 import java.util.Scanner; public class Main { public static void 展开全文

丨阿伟丨

发表于 2025-08-28 12:08:42

题目链接牛牛与切割机题目描述给定一个长度为的序列。将这个序列切割一刀，划分为两个非空的子序列。切割的代价定义为两个子序列元素和的乘积。求最小的切割代价。解题思路本题要求找到一个切割点，使得左右两边子序列元素和的乘积最小。假设我们在第个元素之后进行切割（）。左边的子序列是。展开全文

N_zip

发表于 2025-07-28 15:46:38

#include <climits> #include <iostream> #include <vector> using namespace std; int main() { int n; cin>>n; vector 展开全文

czw230

发表于 2025-08-21 22:37:59

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文

niuke9999

发表于 2025-11-10 13:18:59

#include <stdio.h> #include <stdlib.h> typedef long long ll; int compare(const void*a, const void*b){ ll va = *(ll*)a; ll vb = *( 展开全文

鱼很腾

发表于 2025-11-23 00:45:59

#include <stdio.h> long long f[5000000]={0}; long long sum(int a,int b) { return f[b]-f[a-1]; } int main() { int n; scanf("% 展开全文

何成95

发表于 2025-11-13 20:54:41

n = int(input()) a = list(map(int, input().split())) sum_total = sum(a)#列表中数字总和 sum_left = 0#左边列表数字和 min_mul = float("inf")#最小切割代价 for i in 展开全文

问题信息

数组前缀和京东

难度：

10条回答 53收藏 478浏览

牛牛与切割机

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题