洛谷P4597 序列 sequence
这题是 CF13C 的数据加强版。
题面大意
给定一个序列，每次操作可以把某个数 +1 或 −1。求把序列变成非降数列的最小操作次数，\(n\leq 5\times 10^5\)。
题解
看到题面不难想到一个非常劣的朴素 dp ，无论如何我们先把能想到的东西写出来，设 \(dp[i][j]\) 为到第\(i\)个数，第 \(i\) 个数的值是 \(j\) 的最小操作次数。
考虑优化
对于每一层 \(i\)，把 \(j\) 当做 \(x\) 轴，设函数 \(F_i(j)=\min_{0\leq k\leq j}dp[i-1][k],G(j)=|a_i-j|\)。
当 \(i=1\) 时显然有 \(F_1(j)=0\)。
引理
- 凸性相同的几个分段线性函数的每个点函数值加和后的新函数仍然是分段线性函数，且凸性不变。
对本题 \(G(j)\) 是个绝对值函数的特殊情况很容易通过分类讨论归纳证明。
而一般性情况，对于 oier 来说，这种引理是不必要去理解证明的，所以请自行搜索。
显然 \(|a_i-j|\) 是个下凸的分段线性函数，因此我们可以知道对于每一层 \(i\) 的 dp 值都是下凸的，而取 min 操作会使得 \(F(j)\) 右半部分被拉平。
\(|a_i-j|\) 的加入会使新函数里 \(a_i\) 左边的线段斜率全部 -1，右边的斜率全部+1。
又可以注意到，函数内相邻的两段线段的斜率不会差很大（因为 \(|a_i-j|\) 的加入最多只会使斜率变化 1）。
所以有个很聪明的办法，我们不存线段，而是存斜率 +1 或 -1 的点，只要我们知道什么地方斜率是 0 以及它的函数值，因为 dp 取凸包的最值肯定从斜率为 0 取，我们就可以维护整个凸包了。
举个栗子
那么我们要维护的点集就是 \(\{2,2,4\},F(4)=1\)。
设函数斜率为 \(0\) 直线左端点横坐标为 \(t\)。由于这个下凸（单调不升）的函数的 \(t\) 肯定是点集里x坐标最大的，我们就可以用大根堆维护点集。这时候加入一个 \(|a_i-j|\)，如果 \(a_i\geq t\)，\(a_i\) 左边斜率全 -1，即插入一个新点，\(t'=a_i\)，\(F(t)\) 不变。
如果\(a_i<t\)，同样加入点\(a_i\)以表示左边斜率-1，那么斜率为0的部分就会被抬高斜率+1而被舍弃，所以弹出大根堆堆顶，t不在作为斜率拐点而是新最小值的一部分。且对于新的 \(t'\) 有 \(F_i(t')=F_{i-1}(t)+t-a_i\)。
code
#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
int n,ans;
priority_queue<int> q;
signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<=n;++i){int x;cin>>x;q.emplace(x);//无论如何<ai的斜率-1if(!q.empty()&&x<q.top()){ans+=q.top()-x;//F_{i}(t')=F_{i-1}(t)+t-a_iq.pop();//舍弃掉最右侧斜率拐点，它不再是了q.emplace(x);//右侧斜率全体+1}}cout<<ans;return 0;
}
P4331 [BalticOI 2004] Sequence (Day1)
这个题跟上面的题是一样的，不过你需要一个小 trick 把严格小于变成小于等于。
如果 \(a_i<a_{i+1}\) 则 \(a_i+1\leq a_{i+1}\)，又注意到 \(i+1-i=1\) ，所以 \(a_i-i\leq a_{i+1}-(i+1)\)。
如果是一般的 dp，我们就会把每个 dp 值都存一下它从哪里转移，假设从 \(k\) 转移来
在 slope trick 里，我们只关心极值点。仍然是那两种讨论，我们可以知道，如果 \(a_i>t\)，那么我们是从\(t\)转移而来，应该记录大根堆堆顶；如果 \(a_i<t\)，在 dp 意义下其实是从 \(t'\) 自己转移到 \(t'\)，所以记录每次的堆顶，并从后往前取 min 即可。
code
#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
int n,ans,a[1000010];
priority_queue<int> q;
signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<=n;++i){int x;cin>>x;x-=i;q.emplace(x);if(!q.empty()&&x<q.top()){ans+=q.top()-x;q.pop();q.emplace(x);}a[i]=q.top();}cout<<ans<<endl;for(int i=n-1;i>=1;--i){a[i]=min(a[i+1],a[i]);}for(int i=1;i<=n;++i){cout<<a[i]+i<<endl;}return 0;
}
还有两个例题没写，未完待续……