https://www.luogu.com.cn/problem/P1091

题意：一个序列删除几个使其成为山峰状（中间一个最大，然后两边依次减少），求最少删除个数。

枚举中间值，然后左边求最长上升子序列，右边求最长下降子序列，右边序列的所有值小于左序列的最大值（最后一个）。下降序列的二分，特别注意…被坑死…或者直接逆着求上升序列…用库函数吧…

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
41
42
43
44
45
46
47
48
49
const int INF=0x3f3f3f3f;
const int MAX=100+5;
int n,a[MAX],len1,len2,f[MAX],peak,ans;
int bs(int *f,int l,int r,int x){ //单增序列 
	while(l<r){
		int m=(l+r)/2;
		if(f[m]<x) l=m+1;
		else r=m;
	}
	return f[l]>=x?l-1:l;  
}
int bs2(int *f,int l,int r,int x){ //单减序列 
	while(l<r){
		int m=(l+r)/2;
		if(f[m]<=x) r=m; //' = ' 要放在这里 
		else l=m+1;
	}
	return f[l]<=x?l-1:l;
}
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,0,n)
		sf(a[i]);
	ans = INF;
	fi(ind,0,n){
		len1=0;	
		f[0]=INF;
		fi(i,0,ind+1){
			int x=bs(f,0,len1,a[i]);
			f[x+1]=a[i];
			len1=max(len1,x+1);
		} 
		len2=len1;
		if(ind+1<n) {
			peak=f[len1]; //最大值 
			fi(i,ind+1,n){
				if(a[i] < peak ){ //在小于 peak 的里面找最长递减序列 
					int x=bs2(f,len1,len2,a[i]);
					f[x+1]=a[i];
					len2=max(len2,x+1);
				}
			} 
		}
		ans = min(ans, n-len2-1);
	}
	pf(ans);
	return 0;
}