企业官网建设流程全解析

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

一道思路比较巧妙的题目，我是完全按照算法竞赛入门经典书中的方式去做的。首先用O(n)计算出每个节点作为开头的连续子序列长度，以及作为结尾的连续子序列长度。

然后遍历数组，以为开头的连续子序列长度作为当前值。然后查找从1到i-1作为结尾的最长的值，且结尾的数字小于当前数组的数字。

查找过程使用set数据结构。set中也是在遍历中动态添加数据的，遍历到第i个数据，就添加i-1的数据到set，然后再查找。set中存储的结构按照数组值优先排序，相同时按照【作为结尾的连续子序列长度】排序，升序。每添加一个值时，去除无用的值：

1. set中存在当数组值更小，且子序列长度更长的值时，插入的值无用，应该被抛弃。

2. set中存在数组值更大，且子序列长度更短的值，这些值应被抛弃。

然后set中就仅存在数组值更大，子序列长度也更长的值了。这样我们查找比当前遍历的数组值小的那个元素，就是子序列长度更长的值。

AC代码

#include <stdio.h> #include <string.h> #include <set> using namespace std; #define MAXN 200005 int arr[MAXN]; int n; // leftArr是以i开头的连续子序列长度 // rightArr是以i结尾的连续子序列长度 int leftArr[MAXN], rightArr[MAXN]; struct Stu { int arrV; int value; }; bool operator<(const Stu &left, const Stu right) { if (left.arrV != right.arrV) return left.arrV < right.arrV; return left.value < right.value; } set<Stu> se; void init() { se.clear(); int i, left; memset(leftArr, 0, sizeof(leftArr)); memset(rightArr, 0, sizeof(rightArr)); leftArr[0] = 1; left = 0; for (i = 1; i < n; ++i) { if (arr[i] > arr[i - 1]) { ++leftArr[left]; if (i == n - 1) rightArr[i] = leftArr[left]; } else { rightArr[i - 1] = leftArr[left]; left = i; leftArr[i] = 1; if (i == n - 1) rightArr[i] = 1; } } for (i = 1; i < n; ++i) { if (leftArr[i]) continue; leftArr[i] = leftArr[i - 1] - 1; } for (i = n - 1; i >= 0; --i) { if (rightArr[i]) continue; rightArr[i] = rightArr[i + 1] - 1; } // output /* for (i = 0; i < n; ++i) printf("%2d ", arr[i]); putchar('\n'); for (i = 0; i < n; ++i) printf("%2d ", leftArr[i]); putchar('\n'); for (i = 0; i < n; ++i) printf("%2d ", rightArr[i]); putchar('\n'); */ } int computed() { int i, j, k; bool flag; int value, maxValue = leftArr[0]; for (i = 1; i < n; ++i) { Stu item = {arr[i - 1], rightArr[i - 1]}; se.insert(item); auto ip = se.find(item); flag = false; if (ip != se.begin()) { ip--; // 如果前一个元素的值大于当前元素，那么当前值没有插入的必要 if (ip->value >= item.value) { se.erase(item); flag = true; } else if (ip->arrV == item.arrV) // arr[i]的值相等，且当前值value更大，则前一个值没有存在的必要 se.erase(ip); } if (!flag) { // 向后删除value值更小，没有存在必要的元素 ip = se.find(item); ++ip; while (ip != se.end()) { if (ip->value <= item.value) se.erase(ip++); else break; } } // 对于rightArr[i], 从set中找最合适的元素 ip = se.lower_bound({arr[i], 0}); if (ip == se.begin()) value = ip->value; else { --ip; value = leftArr[i] + ip->value; } if (value > maxValue) maxValue = value; } return maxValue; } int main() { int t, i; scanf("%d", &t); while (t--) { scanf("%d", &n); for (i = 0; i < n; ++i) scanf("%d", &arr[i]); init(); printf("%d\n", computed()); } return 0; }