园林修整 园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了，就需要裁剪；如果太矮了，则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比，所以需要你替他想一种最省力的修整方案。 时间限制：10000 内存限制：65536 输入 输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000)，随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内，同行数字间以空格分隔。 输出 首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号（从 1 开始）。如果解不唯一，输出那个需要最少替换树木的解，题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔，行首尾不得有多余空格。 如果没有树需要调整，则根据树高的升降性质，在一行中输出 Non-ascending（表示“非递增”）或 Non-descending（表示非递减）。 样例输入 样例1： 10 2 3 8 2 4 5 10 1 7 11 样例2： 3 1 2 3 样例输出 样例1： 4 2 3 7 8 样例2： Non-descending 提示 样例1解释： 首先，要将树木修整成按高度非递减的样式，我们需要调整 4 棵树；而要修整成非递增样式，则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次，存在 4 种不同的递增序列解： 1、保持树高为 2、3、4、5、10、11 的树不变，我们需要替换掉高度为 2、1、7 的 3 棵树，因为它们太矮了； 2、保持树高为 2、3、4、5、7、11 的树不变，我们需要替换掉高度为 2、1 的 2 棵树； 3、保持树高为 2、2、4、5、10、11 的树不变，我们需要替换掉高度为 1、7 的 2 棵树； 4、保持树高为 2、2、4、5、7、11 的树不变，我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解，即裁剪编号为 2、3、7（对应高度为 3、8、10）的树，替换掉第 8 棵高度为 1 的树。
正确答案：参考程序（Python）：园林修整。修剪成非递增或非递减，求最少调整树数并输出编号。DP找最长非递减/非递增保留，替换太矮的。样例→4（2 3 7 8）。核心：最长单调子序列修整。
试卷来源：202412 青少年等级考试C/C++真题四级