13023: 【原3023】二哥排队形

题目

题目描述

author: ytytyt13579 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3023

Description

2哥的兄弟们（1哥，2哥，3哥... N哥）站成一排接受幼儿园园长检阅，幼儿园园长要请其中的 N-K 位同学出列，使得剩下的 K 位同学排成这样一个队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T[1]，T[2]，…，T[K]，则他们的身高满足T[1]<...T[i+1]>…>T[K] (1<=i<=K)。也就是说第i位同学最高，然后身高向两边递减 (1<=i<=K)。

Input Format

输入第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(60<=Ti<=260)是第i位同学的身高(厘米)。

Output Format

输出包一个整数，最少需要几位同学出列。

Sample Input

8
185 185 149 200 160 133 196 220

Sample Output

4

数据范围

2<=N<=100 60<=Ti<=260

yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_N 105
#define MAX_T 265
#define lowbit(x) ((x) & (-x))
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
int n;
int a[MAX_N], l[MAX_N], r[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i) a[i] = read();
    for (register int i = 1; i < n; ++i)
        for (register int j = 0; j < i; ++j)
            if (a[i] > a[j])
                l[i] = max(l[i], l[j] + 1);
    for (register int i = n - 2; i >= 0; --i)
        for (register int j = i + 1; j < n; ++j)
            if (a[i] > a[j])
                r[i] = max(r[i], r[j] + 1);
    int ans = 0;
    for (register int i = 0; i < n; ++i)
        ans = max(ans, l[i] + r[i] + 1);
    printf("%d", n - ans);
    return 0;
}