题解 AT5663 【[AGC040E] Prefix Suffix Addition】

Log_x · 2020-04-16 14:05:12 · 题解

Solution

• 在操作所加的序列前添加上若干个 0 就可以看做是任选一个区间加上单调不下降序列或单调不上升序列。

• 由调整法可知，就其中一种操作而言，方案中区间覆盖的范围一定可以做到不相交。

• 设 b_i, c_i 分别表示操作 1 和操作 2 在第 i 个位置加上的权值，满足 \forall 1 \le i \le n, b_i + c_i = a_i。

• 于是在确定 b,c 的情况下，最优的方案就是在将 b,c 中为 0 的元素删去后，将 b 划分为尽量少的单调不下降序列，将 c 划分为尽量少的单调不上升序列。

• 令 a_0 = a_{n + 1} = 0，则最优的答案就为 \sum \limits_{i = 0}^{n}([b_i > b_{i + 1}] + [c_i < c_{i + 1}])。

• 因此朴素的 DP 就是设 f_{i,j} 表示已经处理了前 i 个位置、b_i = j 的最少操作数。

• 由调整法可知， f_{i,j} 在固定 i 时随着 j 的增大单调不上升，并且 f_{i,0} \le f_{i,a_i} + 2， 可以将 f_{i,j} 中权值相同的并成一块进行转移，显然块数只有常数级别。

• 时间复杂度 \mathcal O(n)。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
    char ch;
    while (ch = getchar(), !isdigit(ch));
    res = ch ^ 48;
    while (ch = getchar(), isdigit(ch))
        res = res * 10 + ch - 48;
}

template <class T>
inline T Max(T x, T y) {return x > y ? x : y;}
template <class T>
inline T Min(T x, T y) {return x < y ? x : y;}

using std::vector;
const int N = 2e5 + 5;
int a[N], n;

struct seg
{
    int l, r;

    seg() {}
    seg(int L, int R):
        l(L), r(R) {}

    inline bool Empty()
    {
        return l > r;
    }

    inline seg operator & (const seg &a) 
    {
        return seg(Max(l, a.l), Min(r, a.r)); 
    }

    inline seg operator ^ (const seg &a)
    {
        return a.l == l ? seg(a.r + 1, r) : seg(l, a.l - 1);
    }
};

struct node
{
    seg a;
    int v;

    node() {}
    node(seg A, int V):
        a(A), v(V) {}

    inline bool operator < (const node &a) const
    {
        return v < a.v;
    }
};

vector<node> now, nxt, cur;

int main()
{
    freopen("operate.in", "r", stdin);
    freopen("operate.out", "w", stdout);

    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    now.push_back(node(seg(0, 0), 0));
    for (int i = 1; i <= n + 1; ++i)
    {
        int det = a[i] - a[i - 1];
        seg lim = seg(0, a[i]), tmp;

        cur.clear();
        for (node x : now)
        {
            tmp = seg(0, Min(det + x.a.r - 1, x.a.r - 1)) & lim;
            if (!tmp.Empty())
                cur.push_back(node(tmp, x.v + 2));
            tmp = seg(det + x.a.l, x.a.r - 1) & lim;
            if (!tmp.Empty())
                cur.push_back(node(tmp, x.v + 1));
            tmp = seg(x.a.l, det + x.a.r - 1) & lim;
            if (!tmp.Empty())
                cur.push_back(node(tmp, x.v + 1));
            tmp = seg(Max(x.a.l, det + x.a.l), a[i]) & lim; 
            if (!tmp.Empty())
                cur.push_back(node(tmp, x.v));
        }
        std::sort(cur.begin(), cur.end());
        now.clear();
        for (node x : cur)
        {
            seg res = x.a;
            for (node y : now)
            {
                tmp = res & y.a;
                if (!tmp.Empty())
                    res = res ^ tmp;
                if (res.Empty())
                    break ;
            }
            if (!res.Empty())
                now.push_back(node(res, x.v));
        }
    }
    printf("%d\n", now[0].v);

    fclose(stdin); fclose(stdout);
    return 0;
}