D-Drop Voicing

题目链接：https://ac.nowcoder.com/acm/contest/5670/D
题目大意：
Miyako想通过Drop-2和Invert两种操作把一个给定的排列变成1，2，...，n，连续做任何次数的Drop-2是一个multi-drop，求需要多少次multi-drop

Drop-2操作可以把p-1位放到首位
Invert操作可以把第一位放到最后

解题思路：
每次操作还是通过环来想。
两种操作就是整体在转圈圈和前n-1项在转圈圈

我们思考一下操作的意义，Invert操作不必多说，Drop-2操作让前n-1项转圈相当于在调整pn和其他的相对位置关系。我们只需要相对位置是1，2，...，n就好，相对位置排好后，通过Invert稍微调整一下使得绝对位置1，2，...，n。
那么问题就变为了去找不在正确的相对位置上的点的个数
我们只需要取环上最长的一个上升子序列，然后调整其它数，即可得到答案
复杂度O(n^3)或O(n^2)
代码这里值得再复习的就是绕圈的取模。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;

int a[N], dp[N];
int main()
{
    int n, ans = 0, len = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }    
    for(int i = 0; i < n; i++)
    {
        memset(dp, 0, sizeof(dp));
        for(int j = 1; j <= n; j++)
        {
            dp[j] = 1;
            for(int k = 1; k < j; k++)
            {
                if(a[(i + j) % n + 1] > a[(i + k) % n + 1]) dp[j] = max(dp[j], dp[k]+1);
            }
            len = max(len, dp[j]);
        }
        ans = max(ans, len);
    }
    printf("%d\n",n-ans);
}

LIS那里可以用二分+贪心优化成nlogn
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;

int a[N], dp[N];
int main()
{
    int n, ans = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }    
    for(int i = 0; i < n; i++)
    {
        memset(dp, 0, sizeof(dp));
        int len = 1;
        dp[1] = a[(i + 1) % n + 1];
        for(int j = 2; j <= n; ++j)
        {
            if(a[(i + j) % n + 1] > dp[len])
            {
                dp[++len] = a[(i + j) % n + 1];
            }
            else{
               int m = lower_bound(dp + 1, dp + len + 1, a[(i + j) % n + 1]) - dp;
               dp[m] = a[(i + j) % n + 1];
            }
        }
        ans = max(ans, len);
    }
    printf("%d\n",n-ans);
}