#P12675. 「LAOI-8」Boundary
「LAOI-8」Boundary
题目描述
给定一个长度为 的排列 ,即 包含 中的所有正整数,你可以进行两种操作:
- 将 加上 ,代价为 。
- 将一个 且 的区间 赋值为 ,代价为区间长度。
注意, 也可以进行操作二。
问使得序列 所有元素均变为 的最小代价。
输入格式
本题有多组测试数据。
第一行给定一个正整数 ,表示数据组数。
对于每组数据:
第一行给定一个正整数 ,表示排列 的长度。
第二行给定 个正整数,表示排列 。
输出格式
共 行,一行一个正整数,表示每组数据所需的最小代价。
2
3
1 3 2
9
1 2 3 4 5 6 7 8 9
4
13
提示
样例解释
对于样例组 #1 的第一组测试数据,最小代价按如下操作得到:
- 将 增加 。
- 将 赋值为 。
代价为 ,容易证明该方案最优。
对于样例组 #1 的第二组测试数据,最小代价按如下操作得到:
- 将 和 分别增加 。
- 将 和 赋值为 。
- 将 赋值为 。
代价为 ,容易证明该方案最优。
数据范围
本题采用捆绑测试。
子任务编号 | 特殊性质 | 分值 | |
---|---|---|---|
无 | |||
单调递增 | |||
无 | |||
对于 的测试数据,满足 ,,。