题目描述
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
DP
(最长上升子序列模型) $O(n^2)$
跟登山一样的思路,就是结果算n-res,需要的UU们可以点下面的蓝字传送哦~
AcWing 1014. 登山题解
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int f[N],g[N],w[N];
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
}
for(int i=n-1;i>=0;i--){
g[i]=1;
for(int j=n-1;j>i;j--)
if(w[i]>w[j])
g[i]=max(g[i],g[j]+1);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,f[i]+g[i]-1);
printf("%d",n-res); //这里跟登山不一样,登山是输出res
return 0;
}