【Luogu_P8118】 「RdOI R3.5」Mystery【Slope Trick】【DP】

P8118 「RdOI R3.5」Mystery

题目描述

给出一个长度为 $n$ 的单调不降整数数列 {ai}\{a_i\}{ai​} 和一个整数 $k$。

我们定义两个长度均为 $p$ 的序列 {xi},{yi}\{x_i\},\{y_i\}{xi​},{yi​} 的「差异度」$F(x,y,p)={\sum }_{i=1}^p|x_i-y_i|$。

现在对于每个整数 $l\in [1,n]$，你都需要构造一个长度为 $l$ 的序列 {bl,i}\{b_{l,i}\}{bl,i​}。满足对于任意 $1\le i<l$，$b_{l,i+1}\ge b_{l,i}+k$；且 $F(a_{[1\cdots l]},b_l,l)$ 最小。其中 $a_{[1\cdots l]}$ 表示 {ai}\{a_i\}{ai​} 的长度为 $l$ 的前缀，即 {a1,a2,⋯ ,al}\{a_1,a_2,\cdots,a_l\}{a1​,a2​,⋯,al​}。注意，$b_{l,i}$ 没必要是整数。

输入格式

第一行输入两个整数 $n,k$。
第二行输入 $n$ 个整数，代表 {ai}\{a_i\}{ai​}。
第三行输入一个整数 $T$，代表答案输出方式。具体解释请参考「输出格式」。

输出格式

• 若 $T=0$，则输出 $n$ 个整数，每个整数单独占一行。第 $l$ 行的整数代表 $F(a_{[1\cdots l]},b_l,l)$。
• 若 $T=1$，则你仅需输出一行一个整数，表示 $F(a,b_n,n)$。

输入输出样例 #1

输入 #1

5 2
2 3 4 5 6
0

输出 #1

0
1
2
4
6

输入输出样例 #2

输入 #2

6 2
1 1 4 5 6 8
0

输出 #2

0
2
2
3
4
5

输入输出样例 #3

输入 #3

6 2
1 1 4 5 6 8
1

输出 #3

5

输入输出样例 #4

输入 #4

20 4
4 6 7 9 19 21 30 32 33 35 49 50 58 67 75 77 78 89 91 91
0

输出 #4

0
2
5
10
10
12
12
14
17
22
22
25
25
25
25
27
30
30
32
36

说明/提示

样例解释

样例 #1

如下是一种可能的构造方案：

b1={2}b2={2,4}b3={1,3,5}b4={1,3,5,7}b5={0,2,4,6,8} \begin{aligned} b_1&=\{2\}\\ b_2&=\{2,4\}\\ b_3&=\{1,3,5\}\\ b_4&=\{1,3,5,7\}\\ b_5&=\{0,2,4,6,8\}\\ \end{aligned} b1​b2​b3​b4​b5​​={2}={2,4}={1,3,5}={1,3,5,7}={0,2,4,6,8}​

样例 #2

如下是一种可能的构造方案：

b1={1}b2={0,2}b3={0,2,4}b4={0,2,4,6}b5={−1,1,3,5,7}b6={−1,1,3,5,7,9} \begin{aligned} b_1&=\{1\}\\ b_2&=\{0,2\}\\ b_3&=\{0,2,4\}\\ b_4&=\{0,2,4,6\}\\ b_5&=\{-1,1,3,5,7\}\\ b_6&=\{-1,1,3,5,7,9\}\\ \end{aligned} b1​b2​b3​b4​b5​b6​​={1}={0,2}={0,2,4}={0,2,4,6}={−1,1,3,5,7}={−1,1,3,5,7,9}​

样例 #3

同样例 #2，只不过 $T=1$，你只需要输出 $F(a,b_6,6)=5$ 即可。

数据范围及约定

$$\begin{array}{cccccc}\text{subtask}& \text{分值}& \mathbf{n}\le & \mathbf{T}=& \mathbf{k},{\mathbf{a}}_{\mathbf{i}}\le & \text{subtask 依赖}\\ 1& 30& 100& 0& 100& -\\ 2& 30& 10^5& 0& 10^6& 1\\ 3& 40& 10^6& 1& 10^6& -\end{array}$$

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le k,a_i\le 10^6$，T∈{0,1}T\in\{0,1\}T∈{0,1}。

---

思路：

首先了解Slope Trick
本质上是一种一次分段函数的优化。
拿本题来举例（首先容易想到让$a_i$减去$i\ast k$将题目转化为通过最少次加减1使得序列单调不降），可是设$f_{i,j}$表示到了第$i$位为$j$的最少次数。
可得$$f_{i,j}=min(f_{i-1,k}+|a_i-j|)，1\le k\le j$$
前缀min优化，可得$$f_{i,j}=min(f_{i,j-1},f_{i-1,j}+|a_i-j|)$$
把它写成函数的形式，即令$F(x)=f_{i,j}$，$G(x)=f_{i-1,j}$，$H(x)=|a_i-j|$
得$$F(x)=G(x)+H(x)$$
因为$G(x)$，$H(x)$都为一次分段单凹函数，所以$F(x)$也为一次分段单凹函数，那么接下来使用Slope Trick优化
对于一个一次分段凹函数，我们可以将它记录为在拐点处斜率的加减的形式，如
$$f(x)=\{\begin{array}{r}-x,x<-1\\ x=1,-1\le x\le 1\\ x,x>1\end{array}$$
那么它的记录就是-1,1
表示它在x=-1处斜率加1，在x=1处斜率加1。
如果要合并两个函数，就直接将两个函数的记录数组合并就可以了。
对于这个题目，维护一个凹的分段一次函数，且只有维护左半边，并保持函数的斜率最后一定为0，因为对于后半部分斜率上升的对答案不会有任何影响。
考虑当前函数中最后一段的斜率为0的位置$t$和$a_i$，若$t\le a_i$，则证明$a_i$在当前不需要任何操作，所以贡献为0
若$a_i<t$，则将其升为$t$，产生$t-a_i$的贡献。
然后将$H(x)$加入函数中时，注意如果$t\le a_i$，则只用将$H(x)$的左半部分加入即可，即只用加一次$a_i$，否则加两次。

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>#define ll long longusing namespace std;const ll MAXN = 1e6 + 5;ll n, k, ans, T;
ll a[MAXN];priority_queue<ll> q;int main() {scanf("%lld%lld", &n, &k);for(ll i = 1; i <= n; i ++) scanf("%lld", &a[i]), a[i] -= i * k;scanf("%lld", &T);for(ll i = 1; i <= n; i ++) {if(i == 1) {q.push(a[i]);if(!T) printf("0\n");continue;}if(a[i] >= q.top()) q.push(a[i]);else {ans += q.top() - a[i];q.push(a[i]), q.push(a[i]), q.pop();}if(!T) printf("%lld\n", ans);}if(T) printf("%lld", ans);return 0;
}