AcWing 482. 合唱队形
原题链接
中等
作者:
ZTEG
,
2019-11-08 22:00:42
,
所有人可见
,
阅读 1819
#include<bits/stdc++.h>
using namespace std;
int f[10005],n,t,ff[10005],a[10005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=1;
ff[i]=1;
}
for(int i=1;i<=n;i++)
for(int j=i-1;j;j--)
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1);
for(int i=n;i>0;i--)
for(int j=i+1;j<=n;j++)
if(a[i]>a[j])
ff[i]=max(ff[i],ff[j]+1);
for(int i=2;i<=n;i++)
f[i]=max(f[i],f[i-1]);
for(int i=n-1;i>0;i--)
ff[i]=max(ff[i],ff[i+1]);
for(int i=1;i<=n;i++)
t=max(t,f[i]+ff[i]);
cout<<n-t+1<<endl;
return 0;
}