AT_abc480_g.Zonal Score Minimization
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The score of a sequence of positive integers of length at least 2 is defined as the difference between the maximum and minimum values of the sequence.
You are given a sequence A of N positive integers. Find the minimum possible total score of the contiguous subsequences when A is divided into one or more contiguous subsequences, each of length at least 2.
More formally, find the minimum possible value of ∑k=1K(max(Bk)−min(Bk)) over all positive integers K and sequences of positive integers B1,B2,…,BK, each of length at least 2, such that concatenating B1,B2,…,BK in this order yields A.
长度至少为 2 的正整数序列的得分定义为该序列中最大值与最小值之差。
给定一个由 N 个正整数组成的序列 A。将 A 划分为一个或多个长度均至少为 2 的连续子序列,求这些连续子序列得分总和的最小可能值。
更准确地说,对所有正整数 K 及所有满足以下条件的正整数序列 B1,B2,…,BK(每个序列长度均至少为 2,且按顺序拼接 B1,B2,…,BK 后恰好得到 A),求 ∑k=1K(max(Bk)−min(Bk)) 的最小可能值。
输入格式
The input is given from Standard Input in the following format:
N
A1 A2 … AN
输入从标准输入中按以下格式给出:
N
A1 A2 … AN
输出格式
Print the answer in a single line.
在一行中输出答案。
输入输出样例
输入#1
5 1 3 6 8 9
输出#1
5
输入#2
6 1 4 2 8 7 9
输出#2
5
输入#3
7 10 480 10 480 480 10 480
输出#3
470
说明/提示
Sample 1 Explanation:
If A is divided into (1,3) and (6,8,9), their scores are 2 and 3, respectively, for a total of 5.
It is impossible to make the total score of the contiguous subsequences 4 or less, so the answer is 5.
Constraints
- 2≤N≤2×105
- 1≤Ai≤109
- All input values are integers.
样例 1 解释:
若将 A 划分为 (1,3) 和 (6,8,9),则它们的得分分别为 2 和 3,总得分为 5。
无法使各连续子序列的总得分不超过 4,因此答案为 5。
限制条件
- 2≤N≤2×105
- 1≤Ai≤109
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?