MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 UVA1471 【防线 Defense Lines】

posted on 2019-02-15 11:41:06 | under 题解 |

预先处理出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$

#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;
}