CF原教程：[Tutorial] Slope Trick - Codeforces
目前做的题都是与\(|x-k|\)有关，转移时主要关注最低点，用堆上的每个元素代表一次斜率\(+1\)，但是具体最低点多高不太好搞。
据说有的毒瘤题得拿splay维护。。感觉自己不太行
因为网上题解我有很多都看不懂所以就来写这个了。。当然我对slope trick理解不深所以写的很垃圾。
CF713C Sonya and Problem Wihtout a Legend
这个wihtout是出题人故意打错的吗
先将a[i]-=i，然后条件变为不降。
设\(dp_{i,j}\)表示到\(i\)位置结尾数字为\(j\)的最小代价，则$dp_{i,j}=\min\limits_{k<=j} dp_{i-1,k}+|j-a_i| $
写成函数\(f_i(x)=\min\limits_{y \le x} f_{i-1}(y)+|x-a_i|\)
我们要支持维护一个凸函数，加上\(|x-k|\)，求前缀\(min\)。
考虑维护一个堆，堆中每个元素代表从这里开始折线的斜率\(+1\)，每次加\(|x-k|\)就相当于加入两个\(k\)，求前缀\(min\)则需要把所有斜率大于\(0\)的给推成\(0\)。
每次加入两个\(a_i\)后会有恰好一个斜率为\(1\)的后缀，从堆中弹掉即可。
问题是这个堆只维护了凸函数的形状，也就是每个位置相对于最低位置的高度，并没有告诉我们最低位置的值。
于是我们每次加\(|x-k|\)后算一下它导致最低处上升了多少即可。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define ll long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=3010;
priority_queue<int>q;
int n,a[MAXN];ll ans;
main(){
n=read();
fp(i,1,n)a[i]=read()-i;
q.push(a[1]);
fp(i,2,n){
q.push(a[i]);q.push(a[i]);
ans+=q.top()-a[i];q.pop();
}
printf("%lld\n",ans);
return 0;
}
CF1534G A New Beginning
考虑曼哈顿距离转成切比雪夫距离，就是把\((x,y)\)转成\((\dfrac{x+y}{2},\dfrac{x-y}{2})\)（或者转成\((x+y,x-y)\)后答案除以二）
之后发现存在一种最优方案使得我们只在横坐标相等时才种土豆。
令走到\((x,y)\)代价最小值为\(dp_{x,y}\)则\(dp_{x,y}=\min\limits_{y-(x-p)\le k\le y+(x-p)} dp_{p,k}+|Y_i-y|\)
其中\(p\)指按\(x\)坐标排好序后上一个点的\(x\)坐标。
这个凸函数中间有一段斜率为\(0\)的最小值，把这个凸函数分成了两部分。
容易发现这个取\(\min\)的过程相当于左半边向左平移\(x-p\),右半边向右平移\(x-p\)，这个打个标记即可。具体还发现目前所有标记的总和恰好等于当前的\(x\)。
要分这个\(Y_i\)是在左半部分还是右半部分还是中间最小值那段讨论（不过好像只需要考虑两种情况就行。。算了不管了）
加入在左半部分，在堆中先插入两个\(Y_i\)，然后末尾会翘起来成为斜率为\(1\)，分给右半部分就行。
和上题一样，我们还要顺便维护最低位置的值。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define ll long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=8e5+10;
int n;ll ans;
struct poi{
int x,y;
bool operator<(const poi &b)const{return x<b.x;}
}a[MAXN];
priority_queue<int>pl;
priority_queue<int,vector<int>,greater<int> >pr;
main(){
n=read();
fp(i,1,n){
int x=read(),y=read();
a[i]={x+y,x-y};
}
sort(a+1,a+1+n);
pl.push(a[1].y+a[1].x);pr.push(a[1].y-a[1].x);
fp(i,2,n){
int x=a[i].x,y=a[i].y;
if(pl.top()-x>=y){
pl.push(y+x);pl.push(y+x);int t=pl.top()-x;
ans+=t-y;pl.pop();pr.push(t-x);
}
else if(pr.top()+x<=y){
pr.push(y-x);pr.push(y-x);int t=pr.top()+x;
ans+=y-t;pr.pop();pl.push(t+x);
}
else pl.push(y+x),pr.push(y-x);
}
ans/=2;
printf("%lld\n",ans);
return 0;
}
[APIO2016]烟火表演
我真是菜的离谱。。
虽然那个转移式子非常的复杂但是那个函数连续，所以还是只需要关心
转折点就行，所以代码还是很好写的。
不过这个就不用维护最低点的值了，毕竟最后求答案时\(f(0)\)是知道的，推一遍就行了。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define ll long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=6e5+10;
int ls[MAXN],rs[MAXN],d[MAXN],a[MAXN],fa[MAXN],n,m,deg[MAXN],rt[MAXN],cnt;
ll ans,val[MAXN];
int merge(int x,int y){
if(!x||!y)return x|y;
if(val[x]<val[y])swap(x,y);
rs[x]=merge(rs[x],y);
if(d[ls[x]]<d[rs[x]])swap(ls[x],rs[x]);
d[x]=d[rs[x]]+1;
return x;
}
void pop(int &o){o=merge(ls[o],rs[o]);}
main(){
n=read();m=read();
fp(i,2,n+m){
fa[i]=read();a[i]=read();
ans+=a[i];++deg[fa[i]];
}
fd(u,n+m,2){
if(u<=n)fp(kk,1,deg[u]-1)pop(rt[u]);
ll R=val[rt[u]];pop(rt[u]);ll L=val[rt[u]];pop(rt[u]);
int x=++cnt,y=++cnt;val[x]=L+a[u];val[y]=R+a[u];
rt[u]=merge(rt[u],merge(x,y));
rt[fa[u]]=merge(rt[fa[u]],rt[u]);
}
fp(k,1,deg[1])pop(rt[1]);
while(rt[1])ans-=val[rt[1]],pop(rt[1]);
printf("%lld\n",ans);
return 0;
}