题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
#include <iostream> using namespace std; #include <bits/stdc++.h> int main() { int n; cin>>n; vector<int>heights(n); for(int i = 0; i < n; i++){ cin>>heights[i]; } vector<int>dp1(n,1),dp2(n,0); for(int i = 1; i < n; i++){ for(int j = 0; j < i; j++){ if(heights[j] < heights[i]){ dp1[i] = max(dp1[j]+1,dp1[i]); } } } for(int i = n - 2; i >= 0; i--){ for(int j = n - 1; j > i; j--){ if(heights[j] < heights[i]){ dp2[i] = max(dp2[j]+1,dp2[i]); } } } int MAX =INT_MIN; for(int i = 0; i < n; i++){ dp1[i] += dp2[i]; MAX = max(MAX,dp1[i]); } cout<<n-MAX<<endl; return 0; } // 64 位输出请用 printf("%lld")