dp与找规律

题目来源：https://ac.nowcoder.com/acm/contest/5670#submit/%7B%22problemIdFilter%22%3A209988%2C%22statusTypeFilter%22%3A5%7D
题意：
给你一个p的全排列，有两种操作：
选择倒数第二个挪到第一个
把第一个挪到最后一个
如果是连续的第一种操作，则只花费1，第二种操作不花费。
问最少的花费使得p的全排列变成一个顺序的排列。

题目思路：
最少花费，分析了一下，要了解这个两个操作的本质，其实画了一下发现，实际是把最后一个数挪到前面任意两个数之间，那么思路就是：因为任意一个数花费为0可以成为最后一个，而最后一个数花费为1就可以挪到任意两个数之间，我们要求这个是一个升序，所以先找到最长的升子序列，剩下的数就是结果，相减。
算法：dp，规律

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll
#define N 1010
int a[N*2],dp[N],n,b[N];

int solve()
{
    for (int i = 1;i <= n;i++)  
    dp[i] = inf;
    for (int i = 1;i <= n;i++) 
    *lower_bound(dp +1 , dp + n + 1, a[i]) = a[i];
    return lower_bound(dp + 1, dp + n + 1, inf) - dp - 1;
}

int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) 
    cin>>a[i];
    for (int i = 1; i <= n; i++) 
    a[i + n] = a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, solve());
        for(int j = 1; j <n+1; j++){
            b[j] = a[j];
        }
        for(int j = 1; j < n+1; j++)
    {
            a[j] = b[j + 1];
        }
        a[n] = b[1];
    }
    cout<<n-ans<<endl;
    return 0;
}