A33798. 公园树木
填空题
困难
知识点
题目描述
公园树木
题目描述
某公园有N（3≤N≤50）棵树排成一排，已知每棵树的高度。现要去掉一些树，使得剩下树的高度从左至右呈现先递增再递减的规律（即剩余的树中仅有一棵最高的树，且它左侧的所有树中后一棵树都要比前一棵树高，它右侧的所有树中后一棵树都要比前一棵树矮）
给出N棵树的高度（高度单位：m，1.0≤每棵树高度≤100.0，保留一位小数），请你计算出最少去掉几棵树才能使这排树呈现先递增再递减的规律，如果不能呈现则输出-1（只有递增或者只有递减都为不能呈现）。
例如：N=10，10棵树的高度从左到右依次为1.0、2.3、1.2、1.7、1.1、2.0、1.8、1.8、1.2、1.9。
要使这排树呈现先递增再递减的规律，最少去掉4棵树，去掉的编号分别为2、5、8、10。
剩余树的高度依次为1.0、1.2、1.7、2.0、1.8、1.2，最高树为2.0，其左侧树的高度依次为1.0、1.2、1.7、2.0，呈现递增趋势（从左至右且包含最高树）；其右侧树的高度依次为2.0、1.8、1.2，呈现递减趋势（从左至右且包含最高树）。
输入描述
第一行输入一个正整数N（3≤N≤50），表示这排树的数量
第二行输入N个数（1.0≤每个数≤100.0，保留一位小数），表示每棵树的高度，每个数之间以一个空格隔开
输出描述
输出一个整数，表示最少去掉几棵树才能使这排树呈现先递增再递减的规律，如果不能呈现则输出-1
样例输入
10
1.0 2.3 1.2 1.7 1.1 2.0 1.8 1.8 1.2 1.9样例输出
4参考答案
#include<iostream>
using namespace std;
int f1[51], f2[51];
double t[51];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> t[i];
f1[i] = 1;
f2[i] = 1;
}
int cnt = 0, maxlen_i = 0, maxlen_d = 0;
for (int i = 0; i < n; i++) {
int maxl_i = 1;
for (int j = 0; j < i; j++) {
if (t[j] < t[i])
maxl_i = max(maxl_i, f1[j] + 1);
}
f1[i] = maxl_i;
maxlen_i = max(maxlen_i, maxl_i);
}
for (int i = n - 1; i >= 0; i--) {
int maxl_d = 1;
for (int j = n - 1; j > i; j--) {
if (t[j] < t[i])
maxl_d = max(maxl_d, f2[j] + 1);
}
f2[i] = maxl_d;
maxlen_d = max(maxlen_d, maxl_d);
}
int maxcnt = f1[0] + f2[0];
for (int i = 1; i < n; i++) {
maxcnt = max(maxcnt, f1[i] + f2[i]);
}
if (maxlen_d == n or maxlen_i == n)
cout << -1;
else
cout << (n - maxcnt + 1);
return 0;
}
上一题
下一题