[ZJOI2020] 序列
_ANIG_
·
·
题解
传送门
某天，ANIG 打开了和蔼可亲的教练准备的模拟赛。
在签了 T1，果断放弃大模拟 T2 后，ANIG 打开了 T3：
ANIG 感受到，这是一道难度接近 ZJOID1T3 的题。
由于 ANIG 很菜，所以这种难度的题是 ANIG 不可能会做的。
但是回去做 T2 大模拟对 ANIG 来说是不可能的。
所以可怜的 ANIG 只好开始思考 T3 暴力。
ANIG 发现自己甚至不会写暴力。
于是 ANIG 只能从这个问题的弱化版开始思考：
假设题中的操作分别是操作 1,2,3。
如果只存在操作 1，如何做？
也就是给定一个数列，每次可以选定一个区间整体减去 1，求使数列全部归零的最小操作次数。
看到区间减 1 操作，不禁让 ANIG 想起来了维护这个操作的经典技巧：差分。
对原数列进行差分，则区间 [l,r] 减 1 操作等价于在差分数组上让第 l 项减 1，第 r+1 项加 1。
如果差分数组上每个原来是正数的位置都没有经历加 1 操作，每个原来是负数的位置都没有经历减 1 操作，则这样操作肯定是最优的，总操作次数就是所有正数的和。
并且由于每个元素都大于等于 0，所以差分数组的每个前缀和都非负，也就是每个前缀的正数和都不小于负数和，所以最优的方案一定存在。
这样，ANIG 惊奇的发现自己解决了这个问题：
答案就是原序列差分数组的所有正数的和，也就是 \sum\limits_{a_i>a_{i-1}}a_i-a_{i-1}。
ANIG 开始思考剩余两个子问题，他发现如果只考虑奇数位和只考虑偶数位，也能用类似的方法解决。
也就是说，如果已经确定每个位置被每个操作减了几次，那么 ANIG 就能用上文的方法算出来答案。
这样，只需要 dfs 枚举每个位置被每个操作减了几次，就能得到完整的暴力了。
现在，有了 10pts，ANIG 开始朝着 30pts 进发。
既然是最优化问题，ANIG 决定从 dp 入手。
他观察暴力的计算答案的部分，认为可以把这部分在 dp 的过程中计算。
也就是让 f_i 表示已经计算了所有操作对应的差分数组的前 i 项的正数的和的最小值。
为了计算，dp 数组中还要记下每个操作在第 i 个数前能执行的最后一个数上被执行的次数。
由于每个位置只能被执行两种操作，所以可以只记其中一种，再用总数减去这种的次数就能得到另一种的次数。
这样，ANIG 惊奇的发现他成功设计出了 dp 状态：
转移的时候，枚举第 $i$ 位被操作 $1$ 执行的次数 $l$，则
$$f_{i,k,l}=\min\{f_{i-1,j,k}+\max(l-k,0)+\max((a_i-l)-(a_{i-2}-j),0)\}$$
就这样，ANIG 惊奇的发现他得到了复杂度 $O(nV^3)$ 的做法，得到了 30pts。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,inf=1e18;
int t,n,w[N],f[205][205][205],m,res;
signed main(){
cin>>t;
while(t--){
cin>>n;
m=0;
res=inf;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=0;i<=w[1];i++){
for(int j=0;j<=w[2];j++){
f[2][i][j]=i+max(j-i,0ll)+w[1]-i+w[2]-j;
}
}
for(int i=3;i<=n;i++){
for(int j=0;j<=w[i-2];j++){
for(int k=0;k<=w[i-1];k++){
for(int l=0;l<=w[i];l++){
f[i][k][l]=min(f[i][k][l],f[i-1][j][k]+max(l-k,0ll)+max((w[i]-l)-(w[i-2]-j),0ll));
}
}
}
}
for(int i=0;i<=w[n-1];i++)for(int j=0;j<=w[n];j++)res=min(res,f[n][i][j]);
cout<<res<<"\n";
}
}
```
此时的 ANIG 已经准备心满意足地去睡觉了。
在开始睡觉之前，他决定观赏一下这个 dp 数组。
由于这个数组是三维的，所以可以看作由 $n$ 个 $V\times V$ 的矩形构成。
ANIG 很好奇这些矩形是什么样的。
于是他把这些矩形输出，随便挑了一个好看的矩形，得到了这样的矩阵：
```
167 168 169 170 171 172 173 174 175
166 166 167 168 169 170 171 172 173
165 165 165 166 167 168 169 170 171
164 164 164 164 165 166 167 168 169
163 163 163 163 163 164 165 166 167
162 162 162 162 162 162 163 164 165
161 161 161 161 161 161 161 162 163
160 160 160 160 160 160 160 160 161
159 159 159 159 159 159 159 159 159
158 158 158 158 158 158 158 158 158
157 157 157 157 157 157 157 157 157
156 156 156 156 156 156 156 156 156
155 155 155 155 155 155 155 155 155
154 154 154 154 154 154 154 154 154
154 153 153 153 153 153 153 153 153
154 153 152 152 152 152 152 152 152
154 153 152 151 151 151 151 151 151
154 153 152 151 150 150 150 150 150
154 153 152 151 150 149 149 149 149
154 153 152 151 150 149 148 148 148
154 153 152 151 150 149 148 148 148
154 153 152 151 150 149 148 148 148
154 153 152 151 150 149 148 148 148
154 153 152 151 150 149 148 148 148
155 154 153 152 151 150 149 148 148
156 155 154 153 152 151 150 149 148
157 156 155 154 153 152 151 150 149
```
ANIG 惊奇的发现这个矩阵非常美观。
他发现这个矩阵的数的极差比较小，经过更仔细的观察发现这个矩阵的每一行和每一列都是先递减，然后不变，最后递增。
“这么美观的矩形转移的过程一定也很美观吧。”ANIG 心想。
于是他决定手玩一下转移过程。
他观察了一下自己的转移式：
$$f_{i,k,l}=\min\{f_{i-1,j,k}+\max(l-k,0)+\max((a_i-l)-(a_{i-2}-j),0)\}$$
他发现 $\max(l-k,0)$ 这一项可以提出来。
于是转移式变成：
$$f_{i,k,l}=\min\{f_{i-1,j,k}+\max((a_i-l)-(a_{i-2}-j),0)\}+\max(l-k,0)\}$$
拆开括号，转移式变为：
$$f_{i,k,l}=\min\{f_{i-1,j,k}+\max(a_i-l-a_{i-2}+j,0)\}+\max(l-k,0)\}$$
ANIG 发现，在求 $f_{i,k,l}$ 时，需要遍历 $f_{i-1}$ 的第 $k$ 列，然后求出来每一项加上一个系数的最小值。
ANIG 还发现，在从上往下枚举这一列的值的时候，这个系数刚开始一直是 $0$，从某个位置开始每次加 $1$。
而这一列的前半部分每次减至少 $1$，而系数却每次加最多 $1$，所以即使加上系数也不能让前半部分的数变得比后面的数更小。
这种情况在到达第一个最低点时发生改变。
第一个最低点后面的数原本的值和加的系数都不小于第一个最低点。
也就是第一个最低点原本的值加上系数后依旧是这一整列的最小值。
所以只需要提前求出来每一列的第一个最小值，然后让 $f_{i,k,l}$ 直接从这个位置转移过来就行了。
设 $g_{i,k}$ 表示第 $i$ 个矩阵第 $k$ 列的第一个最小值的位置。
这样，总复杂度就优化为了 $O(nV^2)$。
到这里，可以发现每一列只有最小值是有用的。
于是，ANIG 开始猜测，只有整个矩阵的全局最小值才是有必要保留的。
经过实验，ANIG 惊奇的发现这个结论是正确的。
于是 ANIG 打算新开一个数组，用 $dp_i$ 表示第 $i$ 个矩阵的全局最小值，而原数组 $f$ 就没用了，因为 ANIG 可以只保留所有全局最小值。
于是，ANIG 不在执着于求出每个 dp 值，而是想办法只求出来所有全局最小值。
ANIG 决定，先尝试对每一行求出来这一行的最小值。
假设现在要求 $f_i$ 的第 $k$ 行的最小值，设 $g_{i-1,k}=t$，则等价于求 $\min\limits_{l=0}^{a_i}\{dp_{i-1}+\max(a_i-l-a_{i-2}+t,0)+\max(l-k,0)\}$。
ANIG 惊奇的发现 $dp_{i-1}$ 与 $l$ 无关，所以只需要求 $\max(a_i-l-a_{i-2}+t)+\max(l-k,0)$ 的最小值即可。
设 $A=a_i-a_{i-2}+t$，则相当于求 $\max(A-l,0)+\max(l-k,0)$ 的最小值。
这个式子的最小值并不难求。
经过打表，ANIG 惊奇的发现使得这个式子最小的 $l$ 满足 $\min(A,k)\le l\le \max(A,k)$。
随便挑一个范围内的数带进去就能得到第 $k$ 行的最小值。
ANIG 选择把 $k$ 带进去得到 $dp_{i-1}+\max(a_i-a_{i-2}-k+t)$。
这样，ANIG 就能对每一行快速求出来最小值啦。
下面，ANIG 面临的问题就是如何求出来那些行存在全局最小值。
也就是要求 $\min\limits_{k=0}^{a_{i-1}}\{dp_{i-1}+\max(a_i-a_{i-2}-k+g_{i-1,k})\}$。
ANIG 很好奇，究竟是怎样的行才能存在全局最小值，然后他打了个表，ANIG 惊奇的发现存在全局最小值的行是一个区间。
可以如何求出来这样的区间，ANIG 没有头绪。
写到这里，ANIG 突然发现自己忽略了一个关键的问题：
他还没有求出 $g$ 数组！
于是 ANIG 开始思考如何求出来数组 $g$。
他枚举每一列，现在要求出来第 $i$ 个矩阵的第 $l$ 列中第一个全局最小值的位置。
ANIG 先思考最朴素的做法，也就是枚举每一行，然后判断一个位置是否是全局最小值。
ANIG 惊奇的发现，要判断一个位置是否是全局最小值，只需要判断这个位置所在的行是否存在全局最小值，然后判断这个位置是否是这一行的最小值即可。
而这两个问题都已经在上文解决了！
所以，若第 $k$ 行满足 $k$ 属于存在全局最小值的区间，并且 $\min(A,k)\le l\le \max(A,k)$，那么第 $k$ 行第 $l$ 列就是全局最小值。
可是这样还是太低效了。
于是 ANIG 开始寻找 $\min(A,k)$ 和 $\max(A,k)$ 的性质。
于是 ANIG 打了个关于 $\min(A,k)$ 的表，结果惊奇的发现 $\min(A,k)$ 是单调不降的！
“难道前一项的区间是完全包含后一项的吗？”ANIG 心想。
于是，他尝试找到存在全局最小值的行的最小值，只判断这一行的第 $l$ 列是否是全局最小值。
经过实验，ANIG 惊奇的发现这个猜想是正确的。
这样，就能轻易的求出 $g$ 了，只需要 $\min(A,k)\le l\le \max(A,k)$，就有 $g_{i,l}=L$，其中 $L$ 是存在全局最小值的行的最小值。
于是，ANIG 惊奇的发现，$g_{i,l}$ 要么不存在，要么等于一个常数！
那么上文没有解决的 $\min\limits_{k=0}^{a_{i-1}}\{dp_{i-1}+\max(a_i-a_{i-2}-k+g_{i-1,k})\}$ 中的 $g_{i-1,k}$ 就能替换成常数 $r$。
则问题转化为求出满足 $dp_{i-1}+\max(a_i-a_{i-2}-k+r)$ 最小的 $k$。
ANIG 惊奇的发现 $dp_{i-1}$ 和 $a_i-a_{i-2}+r$ 都与 $k$ 无关。
设 $A=a_i-a_{i-2}+r$，等价于求 $\max(A-k,0)$ 的最小值。
这个问题已经弱到连 ANIG 都会做了。
就这样，ANIG 惊奇的发现他的程序时间复杂度已经降到了 $O(n)$，并且在提交过后他惊奇的发现自己通过了这道题。
相信通过阅读这篇题解，你一定学会如何场切 ZJOID1T3 了吧！
你还在等什么，快去 AK ZJOI 吧！
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int t,n,w[N],dp[N],g1[N],g2[N],g[N];
signed main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
memset(dp,0x3f,sizeof(dp));
if(w[2]>=w[1]){
dp[2]=w[2];
g1[2]=w[1];
g2[2]=w[2];
g[2]=w[1];
}else{
dp[2]=w[1];
g1[2]=w[2];
g2[2]=w[2];
g[2]=w[2];
}
for(int i=3;i<=n;i++){
int lst=0,a=w[i]-w[i-2]+g[i-1];
dp[i]=dp[i-1]+max(a-g2[i-1],0ll);
if(a>g2[i-1])lst=g2[i-1];
else if(a<g1[i-1])lst=g1[i-1];
else lst=a;
int b=lst;
g1[i]=max(min(a,b),0ll),g2[i]=min(max(a,b),w[i]);
g[i]=lst;
}
cout<<dp[n]<<"\n";
}
}
```