a1,a2,a3,a4,a5,a6...an
对ai求出a1到ai的lis,ai+1到an的lds
取所有ai对应的lis+lds最大值
输出n-lis-lds
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n;
double num[1111];
double up[1111];
double down[1111];
const int inf=(1<<31)-1;
int b1(double ss,int Left,int Right)
{
int L=Left;int R=Right;
int mid;
while(L<R)
{
mid=(L+R)>>1;
if(up[mid]>ss)
{
R=mid;
mid=(L+R)>>1;
}
else if(up[mid]==ss)
{
return mid;
}
else
{
L=mid+1;
mid=(L+R)>>1;
}
}
return R;
}
int b2(double ss,int Left,int Right)
{
int L=Left;int R=Right;
int mid;
while(L<R)
{
mid=(L+R)>>1;
if(down[mid]<ss)
{
R=mid;
mid=(L+R)>>1;
}
else if(down[mid]==ss)
{
return mid;
}
else
{
L=mid+1;
mid=(L+R)>>1;
}
}
return R;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("G:/1.txt","r",stdin);
freopen("G:/2.txt","w",stdout);
#endif
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&num[i]);
for(int i=1;i<=n;i++)
{
memset(up,0,sizeof(up));
memset(down,0,sizeof(down));
int lisnum=1;
up[0]=-1;
for(int j=1;j<=i;j++)
{
int index=b1(num[j],0,lisnum);
if(index==lisnum)
lisnum++;
up[index]=num[j];
}
int ldsnum=1;
down[0]=inf;
for(int j=i+1;j<=n;j++)
{
int index=b2(num[j],0,ldsnum);
if(index==ldsnum)
ldsnum++;
down[index]=num[j];
}
lisnum--;ldsnum--;
//cout<<lisnum-1<<' '<<ldsnum-1<<endl;
ans=max(ans,lisnum+ldsnum);
}
printf("%d\n",n-ans);
}