首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7558

最长峰形线 在科学研究中,很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 L 的“峰形线”,是指 L 个数字组成的有序序列 { D1, …,…

最长峰形线

在科学研究中,很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 L 的“峰形线”,是指 L 个数字组成的有序序列 { D1, …, DL },满足条件:存在下标 i(1 < i < L)使得 D1 < … < Di-1 < Di > Di+1 > … > DL。

顺次给出 n 个数字,你可以从中删掉部分数字,使得剩下的数字能构成峰形线。要求构造出来的峰形线是最长的。当最长峰形线不唯一时,你要输出最对称(即升序和降序两部分长度之差为最小)的那条。

时间限制:7000

内存限制:262144

输入

输入第一行给出一个正个整数 n (3 ≤ n ≤ 104),随后一行给出 n 个在区间 [-10000, 10000] 内的整数,以空格分隔。

输出

首先在一行中输出最长峰形线的长度、峰顶数字的序号(从 1 开始)和它的值,数字间以 1 个空格分隔。如果解不存在,则在一行中输出 `No peak shape`。裁判数据保证输出是唯一的。


样例输入

样例#1:

20

1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1

样例#2:

5

-1 3 8 10 20

样例输出

样例#1:

10 14 25

样例#2:

No peak shape

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;climits&gt; using namespace std;   int main() {     int n;     cin &gt;&gt; n;     vector&lt;int&gt; arr(n);     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; arr[i];     }       if (n &lt; 3) {         cout &lt;&lt; "No peak shape" &lt;&lt; endl;         return 0;     }       // LIS dp (Longest Increasing Subsequence from the left)     vector&lt;int&gt; lis(n, 1);  // lis[i] 表示以 arr[i] 为结尾的最长上升子序列长度     for (int i = 0; i &lt; n; i++) {         for (int j = 0; j &lt; i; j++) {             if (arr[i] &gt; arr[j]) {                 lis[i] = max(lis[i], lis[j] + 1);             }         }     }       // LDS dp (Longest Decreasing Subsequence from the right)     vector&lt;int&gt; lds(n, 1);  // lds[i] 表示以 arr[i] 为开始的最长下降子序列长度     for (int i = n - 1; i &gt;= 0; i--) {         for (int j = n - 1; j &gt; i; j--) {             if (arr[i] &gt; arr[j]) {                 lds[i] = max(lds[i], lds[j] + 1);             }         }     }       int maxLength = 0;     int bestIndex = -1;     int bestValue = INT_MIN;     int bestDiff = INT_MAX;       // 查找峰形线     for (int i = 1; i &lt; n - 1; i++) {         // 如果 arr[i] 是峰顶         if (lis[i] &gt; 1 &amp;&amp; lds[i] &gt; 1) {             int length = lis[i] + lds[i] - 1;  // 总长度             int diff = abs(lis[i] - lds[i]);   // 升降长度差               if (length &gt; maxLength || (length == maxLength &amp;&amp; diff &lt; bestDiff)) {                 maxLength = length;                 bestIndex = i;                 bestValue = arr[i];                 bestDiff = diff;             }         }     }       // 输出结果     if (maxLength == 0) {         cout &lt;&lt; "No peak shape" &lt;&lt; endl;     } else {         cout &lt;&lt; maxLength &lt;&lt; " " &lt;&lt; bestIndex + 1 &lt;&lt; " " &lt;&lt; bestValue &lt;&lt; endl;     }       return 0; }</pre>
这道题暂未补解析。