Drop Voicing
题意思路代码
题意
给定一个长度为n的排列，每次可以做两个操作 1、把排列倒数第二个数放到第一的位置 2、把第一个数放到最后一个位置 连续的操作1视作一次操作。 问最少需要几次操作才能把排列变为全部升序。即12345678……
思路
操作2可看作改变排列的顺序，相当于在圆上绕圈圈，操作1可改变排列的本质。 所以只需要每次进行操作2后求排列的最长上升序列长度，再在这些长度中取最大值，用n减去这个值即可。
此处直接把原数组延拓一倍，然后从0到n求最长上升子序列即可 复杂度O(n3) 不是很理解怎么优化到O(n2)我觉得只能到O(n2log n)吧
代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define PII pair<int,int>
#define fi first
#define se second
int T=1,mod;
int qmi(int a,int b){
int res=1;
while(b){
// if(b&1)res=res*a%mod;
b>>=1;
// a=a*a%mod;
}
return res;
}
inline void Rd(int &res) {
res=0;
int f=1;
char ch=getchar();
while('0'>ch||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')res=(res<<3)+(res<<1)+(ch-'0'),ch=getchar();
res*=f;
}
int a[2*510],dp[2*510];
int n;
int inc(int sta){
for(int i=sta;i<n+sta;i++){
dp[i]=1;
for(int j=sta;j<i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int ans=0;
for(int i=sta;i<n+sta;i++)ans=max(ans,dp[i]);
return ans;
}
void solve(){
Rd(n);
for(int i=0;i<n;i++){
Rd(a[i]);
a[i+n]=a[i];
}
int ans=0;
for(int i=0;i<n;i++)ans=max(ans,inc(i));
ans=n-ans;
printf("%d",ans);
}
signed main(){
// Rd(T);
while(T--){
solve();
}
return 0;
}
