You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

53 lines
1.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
int a[101] = {0};
int dp1[101] = {0};
int dp2[101] = {0};
int main() {
// 输入+输出重定向
freopen("../1278.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
// 从左到右身高递增
for (int i = 1; i <= n; i++) { // 遍历每一个元素
dp1[i] = 1; // 以这个元素结尾的dp数组默认值是1即表示只有它自己一个
for (int j = 1; j <= i - 1; j++) { // 从比它小的每一个数都过来计算一次
// 找到比当前元素小的,并且以那个元素结尾的最长子序列长度+1比现在的大就是猴子选大王找最长的一条
if (a[i] > a[j] && dp1[j] + 1 > dp1[i]) {
dp1[i] = dp1[j] + 1;
}
}
}
// 从右到左
// 从右到左进身高递增
for (int i = n; i >= 1; i--) {
dp2[i] = 1;
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[i] && dp2[j] + 1 > dp2[i]) {
dp2[i] = dp2[j] + 1;
}
}
}
int removeCount = INF;
for (int i = 0; i < n; i++) {
removeCount = min(removeCount, n - (dp1[i] + dp2[i] - 1));
}
cout << removeCount << endl;
// 最后队列中有几个人设为m,则n-m就是出列的人员数量
// 而m是如何来的呢 max(dp1[i],dp2[i])的这个人
int maxx = -1;
for (int i = 1; i <= n; ++i) {
if (dp1[i] + dp2[i] > maxx) maxx = dp1[i] + dp2[i] - 1; // 之所以减1是因为有交集
}
cout << n - maxx << endl;
// 关闭文件
fclose(stdin);
return 0;
}