Liveddd's Blog

愛にできることはまだあるかい

[AGC040E] Prefix Suffix Addition

发表于 更新于 分类于
本文字数： 168 阅读时长 ≈ 1 分钟

DP 优化：将分界点作为状态。

先考虑只有操作一的情况，那么我们每次能够消除一个差分为负的位置，答案为 $\sum_i [x_i>x_{i+1}]$。操作二与操作以类似并且对称，于是还是从这一方面入手。设操作一位置 $i$ 加上了 $y_i$，那么答案为：

相当于求出一个序列 $y$，使得最小化上式值。于是我们考虑朴素 DP，设 $f(i,j)$ 表示填到 $i$，第 $i$ 位填 $j$ 的最小值。 暴力转移即可得到 $\mathcal O(nV)$ 的做法。观察该 DP 的性质，得到：

性质 $1$ : $f(i,x)$ 单调不减。因为随着 $y_i$ 增大，转移代价不增。

性质 $2$：$\displaystyle \max_x f(i,x)-\min_x f(i,x)\le 2$。考虑找到 $\displaystyle \min_x f(i-1,x)$，向 $i$ 转移代价不大于 $2$。

那么每一层不同的答案不超过 $3$，并且单调递增。于是我们只需要记录状态的分界点的答案与位置即可。时间复杂度 $\mathcal O(n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y,f,p0,p1;
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        if(x>y)p1=max(p1,p0+x-y);
        else
        {
            p1=max(p0,p1+x-y),p0+=x-y;
            if(p0<0)f++,p0=p1,p1=x;
        }
        p0=min(p0,y=x),p1=min(p1,x);
    }
    printf("%d",f+(p0<x));
    return 0;
}