题解 | 合唱队形

#include <iostream>
#include <vector>
using namespace std;

typedef struct
{

    int height;//每次输入的身高数据
    int length_up;//到输入该数据为止递增的最大子序列长度
    int length_down;//到输入该数据为止开始递减或已经在递减的最大子序列长度(即先增后减的子序列)
}student;

int main() 
{
    
    int N;
    while (cin >> N)
    {

        vector<student> students;
        for (int i = 0; i < N; i++)
        {

            student temp;
            cin >> temp.height;//输入新数据
            temp.length_up = 1;//输入新数据的初始递增序列仅包含自己，故设为1
            temp.length_down = 1;//输入新数据的初始递减序列仅包含自己，故设为1
            if (i == 0) students.push_back(temp);//对于动态规划的初始设置(即对第一个数据进行预设并直接输入)
            else
            {

                for (int j = students.size() - 1; j >= 0; j--)
                {

                    if (students[j].height < temp.height && students[j].length_up >= temp.length_up) temp.length_up = students[j].length_up + 1;//当新数据的身高比正在比较的当前数据的身高更高时，当前数据仅有递增的可能性，于是循环求出最大的递增子序列
                    if (students[j].height > temp.height && (students[j].length_down >= temp.length_down || students[j].length_up >= temp.length_down)) temp.length_down = max(students[j].length_up + 1, students[j].length_down + 1);//当新数据的身高比正在比较的当前数据的身高更低时，当前数据有递增或递减两种可能性，于是循环求出两种可能性中最大的递减子序列
                }//遍历之前的数据，找出递增、递减的最大子序列并据此计算新数据的最大子序列
                students.push_back(temp);
            }
        }//由动态规划，每输入一个数据，计算新状态下的最优解，共输入N次，故有N次循环

        int maxlength = 1;
        for (vector<student>::iterator iter = students.begin(); iter != students.end(); iter++)
        {

            if (maxlength < iter->length_up) maxlength = iter->length_up;
            if (maxlength < iter->length_down) maxlength = iter->length_down;
        }//找到符合题意的最大序列
        cout << N - maxlength << endl;
    }

    return 0;
}