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 22 is defined as the difference between the maximum and minimum values of the sequence.
You are given a sequence AA of NN positive integers. Find the minimum possible total score of the contiguous subsequences when AA is divided into one or more contiguous subsequences, each of length at least 22.
More formally, find the minimum possible value of ∑k=1K(max⁡(Bk)−min⁡(Bk))\sum_{k=1}^{K}\left(\max(B_k)-\min(B_k)\right) over all positive integers KK and sequences of positive integers B1,B2,…,BKB_1,B_2,\dots,B_K, each of length at least 22, such that concatenating B1,B2,…,BKB_1,B_2,\dots,B_K in this order yields AA.

长度至少为 22 的正整数序列的得分定义为该序列中最大值与最小值之差。
给定一个由 NN 个正整数组成的序列 AA。将 AA 划分为一个或多个长度均至少为 22 的连续子序列,求这些连续子序列得分总和的最小可能值。
更准确地说,对所有正整数 KK 及所有满足以下条件的正整数序列 B1,B2,…,BKB_1,B_2,\dots,B_K(每个序列长度均至少为 22,且按顺序拼接 B1,B2,…,BKB_1,B_2,\dots,B_K 后恰好得到 AA),求 ∑k=1K(max⁡(Bk)−min⁡(Bk))\sum_{k=1}^{K}\left(\max(B_k)-\min(B_k)\right) 的最小可能值。

输入格式

The input is given from Standard Input in the following format:

NN
A1A_1 A2A_2 …\ldots ANA_N

输入从标准输入中按以下格式给出:

NN
A1A_1 A2A_2 …\ldots ANA_N

输出格式

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 AA is divided into (1,3)(1,3) and (6,8,9)(6,8,9), their scores are 22 and 33, respectively, for a total of 55.
It is impossible to make the total score of the contiguous subsequences 44 or less, so the answer is 55.

Constraints

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • All input values are integers.

样例 1 解释:
若将 AA 划分为 (1,3)(1,3) 和 (6,8,9)(6,8,9),则它们的得分分别为 22 和 33,总得分为 55。
无法使各连续子序列的总得分不超过 44,因此答案为 55。

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页