1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<cstdio>
#include<iostream>
using namespace std;
int m,n;
int f[9999],f2[9999],h[9999];
int maxn=-9999;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
f[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(h[i]>h[j])
f[i]=max(f[i],f[j]);
}f[i]++;
}
f2[n]=1;
for(int i=n-1;i>1;i--)
{
for(int j=n;j>i;j--)
{
if(h[i]>h[j])
f2[i]=max(f2[i],f2[j]);
}f2[i]++;
}
for(int i=1;i<=n;i++){
int w=f[i]+f2[i]-1;
//printf("%d %d\n",f[i],f2[i]);
maxn=max(w,maxn);
}
printf("%d",n-maxn);
}
|
求一个单调递增序列，一个单调递减序列，然后枚举1~n，把前面递增的和后面递减的加起来找最大的。
