题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
// HJ24 合唱队.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 #include<iostream> #include<bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n) { //cin >> n; vector<int>num(n, 0); for (int i = 0; i < n; i++) cin >> num[i]; vector<int>dp1(n, 0); vector<int>dp2(n, 0); for (int i = 0; i < n; i++) { dp1[i] = 1; for (int j = 0; j < i; j++) { if (num[i] > num[j]) { dp1[i] = max(dp1[i], dp1[j] + 1); } } } for (int i = n - 1; i >= 0; i--) { dp2[i] = 1; for (int j = n - 1; j > i; j--) { if (num[i] > num[j]) { dp2[i] = max(dp2[i], dp2[j] + 1); } } } int maxlen = 0; for (int i = 0; i < n; i++) { maxlen = max(maxlen, dp1[i] + dp2[i] - 1); } cout << n - maxlen << endl; } return 0; }