【NOIP模拟赛】翻转排序

2014年4月5日1,3250

题目描述

Alex得到了存放着一个1-n排列的容器。这个容器支持的唯一操作,是翻转排列的某一段。思考很久之后,他决定用以下方式让这个排列有序:

1 找到每一个极大的下降子序列(子序列要求连续)

2 对于每个长度大于1的极大下降子序列,对它进行翻转

3 如果排列依然不是有序的,转1

我们举一个例子:初始排列是(5 3 1 4 2)

一开始极大的下降子序列是(5 3 1)(4 2)

把这些序列翻转后得到1 3 5 2 4

接下来的极大下降子序列是(1)(3)(5 2)(4)

翻转后是1 3 2 5 4

接下来的极大下降子序列是(1)(3 2)(5 4)

翻转后是1 2 3 4 5,满足要求

定义翻转一个子序列的费用为1(注意一轮翻转的费用可能大于1),那么上面的费用一共是2+1+2=5。

现在,给你一个排列,你要求出对这个排列排序的费用。

另外题目保证:第一次划分时,所有极大下降子序列的长度都是偶数

输入

第一行一个整数N

第二行表示N个数的排列

输出

所需费用。如果不能排序,输出-1

样例输入

4

3 1 4 2

样例输出

3

数据范围

对于10%的数据,N<=10

对于40%的数据,N<=3000

对于100%的数据,N<=100000

题解

我的想法比较奇怪

如果每次只能翻转俩个,那么显然是求逆序对

而这题每次可以翻转一个递减的序列,如果它的长度为l

则我们多翻转了(l+1)*l/2-1

于是我们再扫一遍将答案减去每一段递减序列的(l+1)*l/2-1