希望能在我的代码上指出错误,谢谢
(用了此题没什么用的优化方案)
(我不会告诉你们是因为我懒得重写)
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int t[100010];
int fun(int n){
int dp[100010];
int len=1;
dp[1]=a[1];
for(int i=1;i<=n;i++){
if(a[i]>dp[len]){
len++;
dp[len]=a[i];
}else{
int l=1,r=len,ans;
while(l<=r){
int mid=(l+r)/2;
if(dp[mid]>=a[i]){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
dp[ans]=a[i];
}
}
return len;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>t[i];
}
int maxx=-1;
int ans1;
int ans2;
for(int ti=2;ti<n;ti++){
for(int i=1;i<=ti;i++){
a[i]=t[i];
}
ans1=fun(ti);
for(int i=n,j=0;i>=ti;i--,j++){
a[j]=t[i];
}
ans2=fun(n-ti);
maxx=max(ans1+ans2-1,maxx);
}
cout<<(n-maxx);
return 0;
}