题面

题目名称防火长城 $gfw$

问题描述

在最近一次战争中，国家被摧毁了。你，这个国家的主人，决定提升首都防火长城的级别。防火长城能力很大一部分是由一排的魔法塔决定的，这一排魔法塔从城市一直延续到北边荒野丛林中。你的顾问告诉你，防火长城的能力其实是只由魔法塔的一个特性决定的：就是最长的连续的并且魔法塔高度是递增的魔法塔序列的长度。（顾问给了一个冗长的解释，但你只要知道这与控制敌军翻墙能力有关就可以了）。

为了提升防火长城的防御等级，你开始了刻苦的谈判，法师最终同意解除一部分魔法塔的封印以便你拆除并提升防御等级。然后其余的魔法塔将会重新合并，并保持相对位置不变。现在，你可以拆除任意数量的魔法塔。但法师又露出了邪恶的笑容，缓缓说道：这些被拆除的塔必须是连续的。

请问，删除一些魔法塔后，新的魔法塔序列中最长的连续的并且魔法塔高度是递增的魔法塔序列的长度最大是多少？

输入格式

第一行一个整数 $n$ ，表示原来有 $n$ 个魔法塔。

第二行 $n$ 个整数，为依次的每个魔法塔的高度Hi

输出格式

一行一个整数，为删除一些塔甚至是不删后最长连续且高度递增的魔法塔序列的长度。

样例

输入

1 2	9 5 3 4 9 2 8 6 7 1

输出

样例解释

删除 $9,2,8$ 后，最长连续且高度递增的序列为 $3, 4, 6, 7$ 长度为 $4$ 。

数据范围

对于 $30 \%$ 的数据，$n≤ 10$ 。

对于 $50\% $的数据，$n≤ 100$ 。

对于 $100\%$ 的数据，$n≤ 200000$。

题解

Sol

$n^2$动态规划

首先，题面的意思就是要找两段长度之和最大的最长连续上升子序列。

最长连续上升子序列是可以直接贪心出来的。如果我们要搞两段，可以类似两段最大字段和的方法，用 $\large f_{0/1,~i}$ 来定义状态，其中的 $0/1$ 就表示现在是在做第一段还是第二段， $i$ 则是现在做到了第 $i$ 个数字。

那么转移很显然：不管是第一段还是第二段如果上一个数比这一个数小，就可以直接伸长一段。或者我们可以从之前第一段的里面把第二段新开出来。具体转移方程就是：

$\Large if ~~ a_i>a_{i - 1}\\\Large\quad \quad ~f_{0,i}=f_{0,i-1}+1;\\\Large\quad\quad f_{1,i}=f_{1,i-1}+1;\\\Large f_{1,i}=\max\limits^{i-1}_{j=1}(f_{0,j}+1)\times[a_i>a_j]$

发现这样是 $O(n^2)$ 的只有 $50pt.$

$n\log n$ 优化动规

发现求最大值的那一维是在求一个类似前缀 $\max$ 的东西，但是又不太一样，因为只有在一定的限制之下才能更新答案。那么我们把 $f_0$ 的值抽象成点，就发现我们要求的是一个点左下方的所有点的个数之和，就是一个简单的二位偏序了。

那么离散化，做一个树状数组求前缀 $max$ 即可。（当然也可以用线段树。）

不管怎么实现都是 $O(n\log n)$ 的。

$code:$

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
#define lln putchar('\n')
#define blk putchar(' ')
#define NO 2000005
#define fi first 
#define se second
#define mp(x, y) make_pair(x, y)
#define fup(i, x, y) for (register int i = x; i <= y; i++)
typedef long long ll;
typedef double db;
using namespace std;
typedef pair<int, int> pii;
inline ll read()
{
    ll ret = 0;
    char ch = ' ', last;
    while (ch < '0' || ch > '9')
        last = ch, ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = (ret << 3) + (ret << 1) + ch - '0', ch = getchar();
    return last == '-' ? -ret : ret;
}
void write(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
// head

int n, a[NO], f[2][NO], c[NO], cnt, d[NO];
// variable

void add(int p, int x)
{
    for (int i = p; i <= n; i += (i & -i))
        d[i] = max(d[i], x);
}
int ask(int p)
{
    int ret = 0;
    for (int i = p; i; i -= (i & -i))
        ret = max(ret, d[i]);
    return ret;
}
void init()
{
    freopen("gfw.in", "r", stdin);
    freopen("gfw.out", "w", stdout);
    n = read();
    fup (i, 1, n)
        c[i] = a[i] = read();
    sort(c + 1, c + n + 1);
    cnt = unique(c + 1, c + n + 1) - c - 1;
    f[0][1] = 1;
    fup (i, 2, n)
    {
        if (a[i] > a[i - 1])
        {
            f[0][i] = f[0][i - 1] + 1;
            if (f[1][i - 1])
                f[1][i] = f[1][i - 1] + 1;
        }
        else
            f[0][i] = 1;
        int pos = lower_bound(c + 1, c + n + 1, a[i]) - c, Max = ask(pos - 1);
        if (Max)
            f[1][i] = max(f[1][i], Max + 1);
        add(pos, f[0][i]);
    }
    int ans = 0;
    fup (i, 1, n)
        ans = max(ans, max(f[0][i], f[1][i]));
    write(ans), lln;
}
// functions

int main()
{
    init();
    return 0;
}
// main

Data

download

题面

题目名称 防火长城 $gfw$