P232 合唱队形

先从前往后扫，再从后往前扫。

#include <iostream>
#include <cstring>
#include <math.h>

using namespace std;

const int N = 1001;

int height[N];
int dp[N];
int dp2[N];

int main(){
    int n;
    while(cin >> n){
        int maxh = 0;
        for(int i = 0; i < n; i++){
            cin >> height[i];
        }
        //int ans1 = 0;
        for(int i = 0; i < n; i++){
            dp[i] = 1;       //初始化
            for(int j = 0; j < i; j++){
                if(height[i] > height[j]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
//         for(int i = 0; i < n; i++){
//             dp2[i] = 1;       //初始化
//             for(int j = 0; j < i; j++){
//                 if(height[i] < height[j]){
//                     dp2[i] = max(dp2[i], dp2[j] + 1);
//                 }
//             }
//         }
        int ans = 0;
        for(int i = n - 1; i >= 0; i--){
            dp2[i] = 1;
            for(int j = n - 1; j > i; j--){
                if(height[j] < height[i]){
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
            ans = max(ans, dp[i] + dp2[i] - 1);
        }
//         int ans = 0;
//         for(int i = 0; i < n; i++){
//             ans = max(ans, dp[i] + dp2[i] - 1);
//         }
        printf("%d\n", n - ans);
    }
    return 0;
}

被注释的部分是我的想法，只是单纯找到最长升序或者降序，而不是求一个数前边的最长升序和后边的最长降序。