P1091合唱队列

原题传送门

思路：
对于原序列求满足 $t_1<···<t_i<t_{i+1}>t_{i+2}>···>t_k(1<=i<=k)$的最长子序列
我们将这个关系式拆成两部分来看，即$t_1<···<t_i<t_{i+1}$,和$t_{i+1}>t_{i+2}>···>t_k$
显然我们容易想到，对于每个$t_{i+1}$我们可以正着看求其最长上升子序列$dp1[i+1]$和倒着看求其最长上升子序列$dp2[i+1]$，那么对于整个序列来说，我们要求的结果就是$dp1[i+1]+dp2[i+1]+1$，
对每个$t_{i+1}$对应的结果，我们求$max$，就是这个序列最后剩下的长度，再用原序列长度减之即可

Code：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int a[N],dp1[N],dp2[N],n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
			if(a[i]>a[j])
				dp1[i]=max(dp1[i],dp1[j]+1);
	for(int i=n-1;i>=1;i--)
		for(int j=n;j>i;j--)
			if(a[i]>a[j])
				dp2[i]=max(dp2[i],dp2[j]+1);
	int temp=0,res=0;
	for(int i=1;i<=n;i++){
		temp=dp1[i]+dp2[i]+1;
		res=max(temp,res);
	}
	cout<<n-res<<endl;
	return 0;
}