AcWing 482. 合唱队形
原题链接
中等
作者:
yinyyy
,
2021-02-04 09:13:06
,
所有人可见
,
阅读 281
#include<iostream>
using namespace std;
const int N=103;
int a[N],h[N];
int f[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<=i-1;j++)
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1);
}
//求从左到Ti最长上升;
for(int i=n;i>=1;i--)
{
h[i]=1;
for(int j=i+1;j<=n;j++)
if(a[i]>a[j])
h[i]=max(h[i],h[j]+1);
}
//求从右到Ti最长上升
for(int i=1;i<=n;i++)
ans=max(ans,f[i]+h[i]-1);
//从右到Ti加上从左到Ti,Ti被算了两次,所以这里减一;
cout<<n-ans;
return 0;
}