题解 UVA1471 【防线 Defense Lines】

预先处理出``f[i]``，和``g[i]``两个数组，分别表示以``a[i]``为开头的递增子串长度和以``a[i]``为结尾的递增子串长度 接下来要做的就是求出$\max (g_i + f_j), i < j$ 考虑只枚举$j$，然后二分查找符合条件的$i$ 如果存在$k < j$使得$a_k \leq a_i, g_k > g_i$，则$i$是没有价值的 为了便于查找，我们应只保留有价值的$i$ 具体维护请看代码 更详细的讲解请参考《算法竞赛入门经典（第二版）》——刘汝佳 $P242$ ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; int read() { int k = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') k = k * 10 + c - 48, c = getchar(); return k * f; } int a[200010]; int f[200010], g[200010]; set < std::pair<int, int> > q; //因为set里的元素是有序的，所以用set维护会比较方便 //pair的第一关键字为a[i]，第二关键字为g[i] //自动按第一关键字排序 int main() { int t = read(); while(t--) { int n = read(); q.clear(); for(int i = 1; i <= n; ++i) a[i] = read(); //求出g[i], f[i] g[1] = 1; for (int i = 2; i <= n; ++i) if (a[i - 1] < a[i]) g[i] = g[i - 1] + 1; else g[i] = 1; f[n] = 1; for (int i = n - 1; i >= 1; --i) if (a[i] < a[i + 1]) f[i] = f[i + 1] + 1; else f[i] = 1; //算法核心 int ans = 1; q.insert(pair <int, int> (a[1], g[1])); //初始化 for(int i = 2; i <= n; ++i) { pair <int, int> x(a[i], g[i]); set <pair <int, int> > :: iterator it = q.lower_bound(x); //二分查找set里第一个大于x的元素 if(it != q.begin()){ //因为是第一个大于x的元素，而我们要最大的小于x的元素，所以地址要减去1，同时应防止RE --it; ans = max(ans, (*it).second+f[i]); //更新答案 if((*it).second >= x.second) continue; //当前枚举的i是否有保存价值 } q.erase(x); q.insert(x); //因为set是不重复的，之前可能会有和a[i]相同的元素，此时g[i]一定是大于之前的g[k]的 //如果不大于的话，在第72行会continue，根本来不到这里 it = ++q.find(x); //去掉后面没有价值的数 for(; it != q.end(); ++it) { if((*it).second <= x.second && (*it).first > x.first) q.erase(it); else break; } //加进集合 q.insert(x); } printf("%d\n", ans); } return 0; } ```