原题链接:[https://ac.nowcoder.com/acm/contest/5670/D]

题目描述：

Inaka创作音乐。今天的排列包括n个音符，用排列p_1,p_2,...p_n表示从低到高的音符。
她的朋友Miyako加入了她的工作并通过以下两个操作更改：

Drop-2：取出第二高音符并将其移至最低位置，即将排列更改为pn-1,p1,p2,...,pn-3,pn-2,pn。
Invert：取出最低音符并将其移至最高位置，即，将排列更改为p2,p3,…,pn-1,pn,p1。

任意数量的连续Drop-2操作都被视为一个multi-drop。 Miyako希望以最少的multi-drop数目将排列更改为有序排列1,2,…,n。请帮助她找到所需的multi-drop数目。

输入描述

第一行包含整数n(2≤n≤500)，即音符数。
第二行包含n个以空格分隔的整数p1,p2,…,pn，即音符的原始排列。输入保证从1到n（包括1和n）的每个整数在排列中恰好出现一次。

输出描述

输出描述：输出一个整数，即将排列更改为有序整数所需的最少的multi-drop的次数。

样例

- 样例1

输入
6
2 4 5 1 3 6
输出
2

说明：

使multi-drop最少,即等于2的最佳解决方案是：

Invert，5次，将排列更改为6,2,4,5,1,3;
Drop-2，3次，将排列更改为4,5,1,6,2,3;
Invert，4次，将排列更改为2,3,4,5,1,6;
Drop-2，1次，将排列更改为1,2,3,4,5,6。

- 样例2

输入
8
8 4 7 3 6 2 5 1
输出
5

说明:

此样例请模仿上述说明自行模拟。

题解思路

~~你在想peach。~~
通过读题后仔细分析可知，Drop-2操作是将序列中的第1~n-1号元素翻转，而Invert操作则是将整个序列进行翻转。

~~运用你们丰富的想象力~~想象一下，把整个序列看做一个转盘，而指向1号位的指针作为这个转盘的指针，如下图所示。
图片说明
当操作Drop-2时，把n抽走，指针向左转动，现在的1号位是曾经的n-1号位；
而执行Invert操作时，不抽走n，指针向右转，现在的n号位是曾经的1号位。
显然与最长不下降子序列相关~~（巨佬告诉的）~~。
目前有已知的O( $图片说明$ )的二分法和一般的O（ $图片说明$ ）。
当然还需要枚举数组起点。
下面欣赏批判展示一下O（ $图片说明$ ）的代码。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n,ans;
int a[550],dp[550];

int main()
{
    int now=-1,lenn=0,mlen=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            dp[i]=1;
            for(int j=1;j<i;j++)
                if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
            ans=max(ans,dp[i]);
        }
//      printf("%d\n",ans);
        int t=a[1];
        for(int i=1;i<n;i++)a[i]=a[i+1];
        a[n]=t;
    }
    printf("%d",n-ans);
}
//第一次写题解可能有点水请不要在意

Drop Voicing