题解：AT_agc040_e [AGC040E] Prefix Suffix Addition

Felix72 · 2025-12-05 11:36:20 · 题解

主观难度评价（参考 \text{LCA} 的题目难度向度，[1, 7] 代表从红到黑）：

首先我们需要注意的是题目的条件自由度高，不易设置转移状态或证明一种贪心策略，此时通常的方法是用性质结论来人为限制/放宽条件，使得条件容易刻画。

具体到这个题，不同的区间可能是重叠的，这很不好刻画。因此我们希望区间尽可能不重叠，然后就能发现对于同一类的区间，确实是可以不重叠的。证明如下：

设我们选定 [l_1, r_1], [1_2, r_2] 两个区间进行单调不降加操作（由于可以加前导 0，我们把前缀操作视为区间操作），假设 l_1 < l_2 < r_1 < r_2，我们调整为对 [l_1, r_1], (r_1, r_2] 操作；假设 l_1 < l_2 < r_2 < r_1，我们调整为对 [l_1, r_2], (r_2, r_1] 操作。容易证明这样仍然合法。

则容易设置 \text{DP} 状态 f_{i, 0/1, 0/1} 表示考虑到第 i 个数字，当前是否存在单增（即单调不降），是否存在单减时最少的序列个数，以及序列末端的最优决策。这里，最优决策值多种能凑出 a_i 的方案中最好的那一种。如 10 = 0 + 10 = 2 + 8，若前一个数属于单增序列，后一个数属于单减序列，显然 (0, 10) 严格优于 (2, 8)。容易发现最优决策唯一。

然而可能存在另一种方式，其序列数只比最优决策多一个，但是却拥有更优秀的决策。如 (2, 0, 10)（三元组的三个元素代表序列数（操作次数），单增的当前数字，单减的当前数字）不一定劣于 (1, 3, 7)。

因此我们对每个 f_{i, 0/1, 0/1} 开一个“备选项”g_{i, 0/1, 0/1} 存储仅仅多出 1 代价时的最优决策即可。不难发现代价多 2 时不可能最优，则该 \text{DP} 可以通过本题。

/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 200010, INF = 1100000000;
int n, a[N];
struct node
{
    int sum, u, d;
    bool operator < (const node &w) const
    {
        if(sum != w.sum) return sum < w.sum;
        else if(u != w.u) return u > w.u;
        else return d < w.d;
    }
    bool operator > (const node &w) const
    {
        if(sum != w.sum) return sum > w.sum;
        else if(u != w.u) return u < w.u;
        else return d > w.d;
    }
    inline void debug() {cerr << "> " << sum << " " << u << " " << d << "   ";}
}; node f[N][4][2];
inline void upd(int i, int j, node nd)
{
    if(nd.sum < f[i][j][0].sum) f[i][j][1] = f[i][j][0], f[i][j][0] = nd;
    else if(nd.sum == f[i][j][0].sum) f[i][j][0] = min(f[i][j][0], nd);
    else if(nd.sum < f[i][j][1].sum) f[i][j][1] = nd;
    else if(nd.sum == f[i][j][1].sum) f[i][j][1] = min(f[i][j][1], nd);
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j < 4; ++j)
            for(int k = 0; k <= 1; ++k)
                f[i][j][k] = {INF, a[i], 0};
    f[0][0][0] = {0, 0, 0};
    for(int i = 0; i < n; ++i)
    {
        for(int mask = 0; mask < 4; ++mask)
        {
            for(int ref = 0; ref < 4; ++ref)
            {
                for(int op = 0; op <= 1; ++op)
                {
                    for(int to = 0; to < 4; ++to)
                    {
                        if(((mask | ref) & to) != to) continue;
                        int cost = f[i][mask][op].sum + __builtin_popcount(ref);
                        int U = ((ref & 2) ? INF : f[i][mask][op].u);
                        int D = ((ref & 1) ? 0 : f[i][mask][op].d);
                        if(to == 0)
                        {
                            if(a[i + 1] == 0)
                                upd(i + 1, 0, {cost, U, D});
                        }
                        else if(to == 1)
                        {
                            if(D <= a[i + 1])
                                upd(i + 1, 1, {cost, U, a[i + 1]});
                        }
                        else if(to == 2)
                        {
                            if(U >= a[i + 1])
                                upd(i + 1, 2, {cost, a[i + 1], D});
                        }
                        else if(to == 3)
                        {
                            if(U + D >= a[i + 1] && D <= a[i + 1])
                                upd(i + 1, 3, {cost, a[i + 1] - D, D});
                            if(U + D <= a[i + 1])
                                upd(i + 1, 3, {cost, U, a[i + 1] - U});
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < 4; ++i)
        for(int j = 0; j <= 1; ++j)
            ans = min(ans, f[n][i][j].sum);
    cout << ans << '\n';
    return 0;
}
/*

*/