#P17896. Absolutely Flat
Absolutely Flat
题目描述
有一个长度为 的正整数数组,其中一些元素缺失。在输入中,缺失的元素用 表示。
对于区间 ,定义它的波动值为区间内最大值与最小值之差:
$$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r).$$给定 个区间 。请将每个缺失元素替换成一个正整数,使这 个区间的波动值之和最小。求这个最小值。
同一个缺失位置只能填一个值,填入的值会同时用于所有包含该位置的区间。已经给出的非零元素不能修改。区间可以重复,重复给出的区间需要重复计入总和。
输入格式
第一行包含两个整数 。
第二行包含 个整数 ,其中 表示该元素缺失。
接下来 行,每行包含两个整数 ,表示一个区间。
输出格式
输出一个整数,表示所有给定区间波动值之和的最小值。
数据范围
- ;
- ;
- 。
样例输入
3 2
1 0 3
1 2
2 3
样例输出
2
样例解释
将缺失元素填为 ,两个区间的波动值都是 ,总和为 。填为 或 也能得到最优答案。