【日记】12.19

12.19

DP

1. P1091：找出最高的合唱队形。

思路：dp1[i]表示以i为最后一个人，1-i中的LIS，dp2[i]表示以i为第一个人，i-n中的LDS。dp1从前往后跑，dp2从后往前跑。注意一下，不是从前往后的LDS。

#include<bits/stdc++.h>
using namespace std;
const int M=140;
int a[M],n,ans[M];
struct LIS{
	int dp[M],d[M];
	void run(){
		int len=0;
		for(int i=1;i<=n;++i){
			int p=lower_bound(d+1,d+len+1,a[i])-d;//找到第一个大于等于a[i]的下标
			dp[i]=p,d[p]=a[i];
			if (p>len)
				len=p;
		}
	}
}L1;
struct LDS{
	int dp[M],d[M];
	void run(){
		int len=0;
		for(int i=n;i>=1;--i){
			int p=lower_bound(d+1,d+len+1,a[i])-d;//找到第一个大于等于a[i]的下标
			dp[i]=p,d[p]=a[i];
			if (p>len)
				len=p;
		}
	}
}L2;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	L1.run(),L2.run();
	int ans=0;
	for(int i=1;i<=n;++i)
		ans=max(ans,L1.dp[i]+L2.dp[i]-1);
	printf("%d
",n-ans);
	return 0;
}