分段得分最小化AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)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 $\sum_{k=1}^{K}\left(\max(B_k)-\min(B_k)\right)$ over all positive integers $K$ and sequences of positive integers $B_1,B_2,\dots,B_K$, each of length at least $2$, such that concatenating $B_1,B_2,\dots,B_K$ in this order yields $A$.
长度至少为 $2$ 的正整数序列的得分定义为该序列中的最大值与最小值之差。
给定一个由 $N$ 个正整数组成的序列 $A$。将 $A$ 划分为一个或多个连续子序列，且每个子序列的长度至少为 $2$，求这些连续子序列的得分总和的最小可能值。
更形式化地说，在所有满足以下条件的正整数 $K$ 以及正整数序列 $B_1,B_2,\dots,B_K$ 中，求 $\sum_{k=1}^{K}\left(\max(B_k)-\min(B_k)\right)$ 的最小可能值：每个序列的长度至少为 $2$，并且按顺序拼接 $B_1,B_2,\dots,B_K$ 后得到 $A$。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$2 \leq N \leq 2 \times 10^5$$1 \leq A_i \leq 10^9$- All input values are integers.
$2 \leq N \leq 2 \times 10^5$$1 \leq A_i \leq 10^9$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入中按以下格式给出：AI (CI翻译)
N
A_1 A_2 \ldots A_NN
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Print the answer in a single line.
在一行中输出答案。AI (CI翻译)
样例
5
1 3 6 8 9
5
6
1 4 2 8 7 9
5
7
10 480 10 480 480 10 480
470
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。