这题不是和登山时一样的吗
直接上传送门
C++代码
#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N],w[N];
int v[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=w[i]=1;//初始为1
}
//计算1~n的最大上升子序列
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
//计算n~1的最长下降子序列
for(int i=n;i>=1;i--)
for(int j=n;j>=i;j--)
if(a[i]>a[j]) w[i]=max(w[i],w[j]+1);
// 计算参观景点的最大值
int mx=0;//mx是参观景点的最大值
for(int i=0;i<=n;i++)
for(int j=i+1;j<=n+1;j++)
if(a[i]<a[j]) mx=max(mx,f[i]+w[j]);
cout<<n-mx<<endl;
return 0;
}