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)。

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];
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() {
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;
}
``````