【题解】合唱队形

合唱队形中，站在C位（最中间）的人应该是最高的，设选择的人为i 。这个人左侧的人的身高应该是一个上升序列，右侧的人的身高应该是一个下降序列，左右侧人的身高都不应该高于t i 。
为了使出列的人最少，第i 人左侧应该取最长上升子序列，右侧应该取最长下降子序列。
求最长上升、下降子序列时，要包括第i 人。这样容易取到以i 为结尾的最长上升子序列，以及以i为起始的最长下降子序列的长度。
我们可以尝试让每个人站C位，让他作为最高的人。如果i 站C位，那么剩下的人数为：以i为结尾的最长上升子序列长度+以i为起始的最长下降子序列的长度-1。因为这两个序列都包含i ，重复统计了i ，所以要减1。
出列的人数就是总人数n减去上面求出的剩下的人数。
求出在每种情况下出列的人数的最小值。

#include<bits/stdc++.h>
using namespace std;
#define N 3005
int main()
{
    int n, t[N], dpu[N], dpd[N], r;//dpu[i]:以i为结尾的最长上升子序列 dpd[i]:以i为起始的最长下降子序列
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> t[i];
    for(int i = 1; i <= n; ++i)//求最长上升子序列
    {
        dpu[i] = 1;
        for(int j = 1; j < i; ++j)
            if(t[j] < t[i])
                dpu[i] = max(dpu[i], dpu[j]+1);
    }
    for(int i = n; i >= 1; --i)//求最长下降子序列
    {
        dpd[i] = 1;
        for(int j = n; j > i; --j)
            if(t[j] < t[i])
                dpd[i] = max(dpd[i], dpd[j]+1);
    }
    r = n;//r:去掉的人数，初值设为最大可能去掉的人数
    for(int i = 1; i <= n; ++i)//让i站C位，看看要去掉多少人
        r = min(r, n-(dpu[i]+dpd[i]-1));//剩下dpu[i]+dpd[i]-1人，去掉n-(dpu[i]+dpd[i]-1)人
    cout << r;
    return 0;
}