简答题
偏难
#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 <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (n < 3) {
cout << "No peak shape" << endl;
return 0;
}
// LIS dp (Longest Increasing Subsequence from the left)
vector<int> lis(n, 1); // lis[i] 表示以 arr[i] 为结尾的最长上升子序列长度
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
lis[i] = max(lis[i], lis[j] + 1);
}
}
}
// LDS dp (Longest Decreasing Subsequence from the right)
vector<int> lds(n, 1); // lds[i] 表示以 arr[i] 为开始的最长下降子序列长度
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (arr[i] > 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 < n - 1; i++) {
// 如果 arr[i] 是峰顶
if (lis[i] > 1 && lds[i] > 1) {
int length = lis[i] + lds[i] - 1; // 总长度
int diff = abs(lis[i] - lds[i]); // 升降长度差
if (length > maxLength || (length == maxLength && diff < bestDiff)) {
maxLength = length;
bestIndex = i;
bestValue = arr[i];
bestDiff = diff;
}
}
}
// 输出结果
if (maxLength == 0) {
cout << "No peak shape" << endl;
} else {
cout << maxLength << " " << bestIndex + 1 << " " << bestValue << endl;
}
return 0;
}</pre>
这道题暂未补解析。