给定一个长度为 n 的排列 A,即 A 包含 [1,n] 中的所有正整数,你可以进行两种操作:
- 将Ai加上 1,代价为 1。
- 将一个Al=Ar且 l!=r 的区间 [l,r] 赋值为 −10^9,代价为区间长度。
注意,Al=Ar=−10^9 也可以进行操作二。
问使得序列 A 所有元素均变为 −10^9的最小代价。
给定一个长度为 n 的排列 A,即 A 包含 [1,n] 中的所有正整数,你可以进行两种操作:
注意,Al=Ar=−10^9 也可以进行操作二。
问使得序列 A 所有元素均变为 −10^9的最小代价。
本题有多组测试数据。
第一行给定一个正整数 T,表示数据组数。
对于每组数据:
第一行给定一个正整数 n,表示排列 A 的长度。
第二行给定 n 个正整数,表示排列 A。
共 T 行,一行一个正整数,表示每组数据所需的最小代价。
2
3
1 3 2
9
1 2 3 4 5 6 7 8 9
4
13
对于样例组 #1 的第一组测试数据,最小代价按如下操作得到:
代价为 1+3=4,容易证明该方案最优。
对于样例组 #1 的第二组测试数据,最小代价按如下操作得到:
代价为 2+4+7=13,容易证明该方案最优。