公园树木 题目描述： 某公园有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
正确答案：求最长严格单峰(先增后减)子序列。inc[i]=以i结尾最长递增，dec[i]=以i开头最长递减；峰值i需两者均≥2，长度=inc+dec-1，答案n-最大长度，无峰则-1。核心：\nif a[j]<a[i]:inc[i]=max(inc[i],inc[j]+1)\nif a[j]<a[i]:dec[i]=max(dec[i],dec[j]+1)\nbest=max([inc[i]+dec[i]-1 for i in range(n)if inc[i]>=2 and dec[i]>=2]or[0])
答案解析
评分标准：
5分：能正确输出第一组数据；
5分：能正确输出第二组数据；
5分：能正确输出第三组数据；
5分：能正确输出第四组数据；
5分：能正确输出第五组数据；
5分：能正确输出第六组数据。
试卷来源：202301(第14届)蓝桥杯C++编程青少组(选拔赛_中高级)真题