[C++知识库]P1091 [NOIP2004 提高组] 合唱队形(最长上升子序列)

P1091?[NOIP2004 提高组] 合唱队形https://www.luogu.com.cn/problem/P1091

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <cstdlib>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 2000010;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)


int n;
int a[MAXN], s1[MAXN], s2[MAXN];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	for (int i = 1; i <= n; i++) {
		s1[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j]) {
				s1[i] = max(s1[i], s1[j] + 1);
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		s2[i] = 1;
		for (int j = n; j > i; j--) {
			if (a[i] > a[j]) {
				s2[i] = max(s2[i], s2[j] + 1);
			}
		}
	}
	int maxx = 0;
	for (int i = 1; i <= n; i++) {
		int tmp = s1[i] + s2[i] - 1;
		maxx = max(maxx, tmp);
	}
	printf("%d", n - maxx);
	return 0;
}