先摆上学习的文章：
感谢dalao们的讲解，还是十分清晰的
斜率优化$DP$的本质是，通过转移的一些性质，避免枚举地得到最优转移
经典题：HDU 3507 （$Print$ $Article$）
状态数$O(N)$，单次转移$O(N)$的做法还是比较容易的
令dp[i]表示打印完第$i$个单词的最小花费，$S[i]$表示$C[1]$到$C[i]$的前缀和，则转移方程为
\[dp[i]=min\{dp[j]+(S[i]-S[j])^{2}\}+M\]
我们想对这个进行优化，显然状态数是没有办法削减的，那么只能考虑：如何不枚举地得到最优转移？
要得到最优转移，首先我们要能够判断两个转移中哪个更优
假如我们分别从$j$、$k$（$j\neq k$）转移来计算$dp[i]$，其中假设从j转移更优，则有
\[dp[j]+(S[i]-S[j])^{2}<dp[k]+(S[i]-S[k])^{2}\]
展开、移项后得到
\[dp[j]-dp[k]+S[j]^{2}-S[k]^{2}<2S[i](S[j]-S[k])\]
我们令
\[f[i]=dp[i]+S[i]^{2}\]
那么则有
\[\frac{f[j]-f[k]}{S[j]-S[k]}<2S[i], k<j\]
\[\frac{f[j]-f[k]}{S[j]-S[k]}>2S[i], k>j\]
（因为$f[i]$、$S[i]$均单调不减，所以除法后的变号能够确定）
左边跟物理中的斜率的表达式十分相似：表示横轴为$S$，纵轴为$f$的平面直角坐标系中，$j$点$(S[j],f[j])$到$k$点$(S[k],f[k])$的斜率
所以我们要找的最优转移j满足，对于所有的$1\le k<j$，$j$点到$k$点的斜率小于$2S[i]$；对于所有的$j<k<i$，$j$点到$k$点的斜率大于$2S[i]$
或者说，过$j$作斜率为$2S[i]$的直线$L$，所有的$k\neq j$均在$L$上方；即斜率为$2S[i]$的扫描线从上向下最后扫到的点
（随便画一下，大概是这个样子；这里不是很关键）
但是，现在离我们真正想出优化的方法还是有些距离的
现在我们考虑一个问题：我们能否根据一些点构成的形状，判断一个点能否成为最优转移？
从简单的三点两线开始吧，不共线的时候共有两种情况（A）、（B）
（A）（B）中两条直线斜率$k_{ij}$、$k_{jk}$的大小关系已经确定了，我们再带入斜率为$x$的直线来讨论一下（直观的方式是，作斜率为$x$的扫描线$L$）
（A）：
$k_{jk}<k_{ij}<x$：若过$k$作斜率为$x$的直线，则$i$、$j$均在直线上方，所以此时$k$最优
$k_{jk}<x<k_{ij}$：这里有两种可能，若$x<k_{ik}$则$i$最优（如第二个图）；若$x>k_{ik}$则$k$最优（这个情况没画）
$x<k_{jk}<k_{ij}$：若过$i$作斜率为$x$的直线，则$j$、$k$均在直线上方，所以此时$i$最优
总之，只要存在三点$i$、$j$、$k$（$i<j<k$）使得$j$在$ik$连线的上方，$j$就不可能是最优转移了
根据这条性质，所有可能是最优转移的点一定构成一个下凸的凸包，形状满足相邻线段斜率单调增（不过这里不需要什么凸包的知识啦，因为我也不会= =）
所以我们可以直接将不可能成为最优转移的$j$全部删去，得到这样的凸包
具体是怎么做的呢？
我们想加入i时，每次选择可用点的最后两个$q[sz-1]$、$q[sz]$，比较$q[sz-1]$与$q[sz]$连线、$q[sz]$与$i$连线的斜率$k_1$、$k_2$
- 若$k_1<k_2$，则直接将$i$加入可用点集$q$
- 若$k_1\ge k_2$，则$q[sz]$是上凸的无用点，直接删去，并继续向前找
于是，（B）成为了删去无用点后、找最优点的简化版问题
（B）：
$k_{ij}<k_{jk}<x$：此时k最优
$k_{ij}<x<k_{jk}$：此时j最优
$x<k_{ij}<k_{jk}$：此时i最优
这里就能发现一个规律：$x$越大，最优转移的点越靠后
所以我们发现，因为$S[i]$是单调不减的，对于最优转移的点，其序号是只增不减的
而最优转移的点数目是$O(N)$规模的，即最优转移最多只会变化$n$次，这样均摊的转移就成功变为$O(1)$！
不过具体怎么找最优转移呢？
若上一个点的最优转移为可用点集中的第$j$个（即$q[j]$），那么我们计算$q[j]$、$q[j+1]$连线的斜率（这里对应的是斜率不等式中$k>j$的情况，不要搞混了）
- 若这个斜率小于$S[i]$，那么$q[j+1]$比$q[j]$更优，并继续比较$q[j+1]$、$q[j+2]$...
- 若这个斜率大于等于$S[i]$，那么$q[j+1]$不比$q[j]$更优，那么对于$i$，最优转移为$q[j]$
（如果这里不等式的右端不是单调不减的$S[i]$，而是一个任意的函数$g(i)$，那么每次选择最优转移点时，应当在当前可用点集中进行二分（比较$q[mid]$与$q[mid+1]$的斜率），这时转移是$O(logN)$的）
代码倒是挺短的...之前一直在看数据结构，突然有点不适应
在理论分析之外，还有些细节问题需要注意
- 在动态维护下凸包时，有可能在删点后之前最优转移指针大于点集大小，此时应该将指针移到点集末尾（如此图）
- 比较斜率时可以开__int128后交叉相乘以避免除法（这样可以防止除$0$）
- 在选择最优的转移时，可以不用比较斜率，转而比较$dp$值会更方便（很实用）
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; typedef long long ll;
const int MAX=; int n,m;
ll s[MAX];
ll dp[MAX]; int q[MAX];// Save available vertices inline ll Calc(int j,int i)// Calculate dp[j]->dp[i]
{
return dp[j]+(s[i]-s[j])*(s[i]-s[j])+m;
} inline ll Up(int i,int j)
{
return dp[i]-dp[j]+s[i]*s[i]-s[j]*s[j];
} inline ll Down(int i,int j)
{
return s[i]-s[j];
} int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
s[i]=s[i-]+x;
} q[]=;
int j=,sz=;// Initially, 0 is in the queue
for(int i=;i<=n;i++)
{
while(j<sz && Calc(q[j],i)>Calc(q[j+],i))
j++;
dp[i]=Calc(q[j],i); while(sz> && Up(q[sz],q[sz-])*Down(i,q[sz])>=Up(i,q[sz])*Down(q[sz],q[sz-]))
sz--;
q[++sz]=i;
if(j>sz)
j=sz;
}
printf("%lld\n",dp[n]);
}
return ;
}
慢慢补点题上来...
一道同样挺裸的题目：洛谷P3159（$HNoi2008$，玩具装箱）
这道题除了斜率式的不等号右边恶心一点以外，其余都跟例题差不多（甚至同样单调不减）
尽管$dp[i]$不一定单调不减，但是我们依然构造的是下凸包，只不过一开始斜率可以为负罢了
不过这题的斜率只能用$double$来比较了（通分必然爆$long$ $long$），有一个好消息是不存在$C_i=0$，所以可以放心地除
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std; typedef long long ll;
const int MAX=; int n,L;
ll s[MAX],dp[MAX]; int sz=;
int q[MAX]; inline ll pow(ll x)
{
return x*x;
} inline ll Calc(int j,int i)
{
return dp[j]+pow(i-j-+s[i]-s[j]-L);
} inline double Slope(int i,int j)
{
return (dp[i]-dp[j]+pow(i+s[i])-pow(j+s[j]))/(double)(i-j+s[i]-s[j]);
} int main()
{
// freopen("input.txt","r",stdin);
scanf("%d%d",&n,&L);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
s[i]=s[i-]+x;
} int j=;
for(int i=;i<=n;i++)
{
while(j<sz && Calc(q[j],i)>Calc(q[j+],i))
j++;
dp[i]=Calc(q[j],i); while(sz> && Slope(q[sz],q[sz-])>=Slope(i,q[sz]))
sz--;
q[++sz]=i;
if(j>sz)
j=sz;
}
printf("%lld\n",dp[n]);
return ;
}
从洛谷上搜“斜率优化”找到的一题：CF 311B （$Cats$ $Transport$）
这题的数据有bug吧，出发时间竟然可以是负数...不要像我一样特判就好...
虽然最后的实现挺裸，但是前面要稍微做点准备
山之间走的时间和猫出现的时间都是假的，我们需要的时间是猫$i$在$t_i$时刻到达某山顶$d_i$反推的出发时间$a_i$，即在时间$a_i$从起点出发能正好捞到猫$i$
将这个时间$sort$一波，那么就可以转化成简单的二维$dp$了
令$dp[i][j]$表示派出第$i$个人、一直捞到猫$j$所需的最小代价，$a[j]$表示要正好捞猫$j$应该出发的时间，$s[j]$表示$a[j]$的前缀和，那么递推式为
\[dp[i][j]=min\{dp[i-1][k]+a[j]\cdot (j-k)-(s[j]-s[k])\}\]
然后两个转移点$k$、$l$中，$k$更优的条件化简后是
\[\frac{dp[i-1][k]-dp[i-1][l]+s[k]-s[l]}{k-l}<a[j],l<k\]
\[\frac{dp[i-1][k]-dp[i-1][l]+s[k]-s[l]}{k-l}>a[j],l>k\]
剩下跟例题就一毛一样了...下一题一定不能找这样的裸题
（话说以前的Div1 B好难啊...现在的就不提了，连我都能做）
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long ll;
const ll INF=1LL<<;
const double eps=0.0000001;
const int MAXN=;
const int MAXM=;
const int MAXP=; int n,m,p;
int pre[MAXN];
int a[MAXM];
ll s[MAXM]; ll dp[MAXP][MAXM];
int q[MAXM]; inline ll Calc(int i,int j,int k)
{
return dp[i-][k]+a[j]*ll(j-k)-(s[j]-s[k]);
} inline double Slope(int i,int j,int k)
{
return double(dp[i-][j]-dp[i-][k]+s[j]-s[k])/(double)(j-k);
} int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
scanf("%d%d%d",&n,&m,&p);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
pre[i]=pre[i-]+x;
}
for(int i=;i<=m;i++)
{
int h,t;
scanf("%d%d",&h,&t);
a[i]=t-pre[h];
} sort(a+,a+m+);
for(int i=;i<=m;i++)
s[i]=s[i-]+a[i]; for(int i=;i<=m;i++)
dp[][i]=Calc(,i,);
for(int i=;i<=p;i++)
{
int pnt=,sz=;
for(int j=;j<=m;j++)
{
while(pnt<sz && Calc(i,j,q[pnt])>Calc(i,j,q[pnt+]))
pnt++;
dp[i][j]=min(INF,Calc(i,j,q[pnt])); while(sz> && Slope(i,q[sz],q[sz-])>Slope(i,j,q[sz])-eps)
sz--;
q[++sz]=j;
if(pnt>sz)
pnt=sz;
}
} ll ans=INF;
for(int i=;i<=p;i++)
ans=min(ans,dp[i][m]);
printf("%I64d\n",ans);
return ;
}
用假算法能过的一道题：洛谷P2305 （$NOI2014$，购票）
算法错没错？错了！值不值得练习？值得！（这里只是为了巩固斜率优化，在细节上已经是不简单的了）
如果没有$l\_v[i]$的限制条件，那么这道题就是一个树上的斜率优化$DP$
我们只要将当前路径（从$1$出发通过$i$的祖先到达$i$）上的节点依次压入一个栈，这时整个问题就变成了栈上的一维的$DP$了：所以我们只讨论一维的实现（但真正把树通过$dfs$拍成一维时，外部和内部的元素的关系会比较tricky）
问题是，加上了$l\_v[i]$的条件以后，假设第一个满足这个条件的节点为$j$，那么我们需要的下凸包是从$j$开始的；而我们之前的所有问题，下凸包都是从$1$开始的
这个博客里有比较清晰的图示，可以参考一下：zzyu5ds：NOI2014购票
那么应该怎么做呢？我们可以考虑从几个分开的下凸包中求出最优转移（说不定这种处理方法在哪题就是正解了呢）
我们这样存储下凸包：
开一颗线段树，其中每个节点都是一个$vector$（这样说比较容易懂，但最后会用大小为$NlogN$的数组实现），存储其对应区间中，以区间开头为起点的下凸包
这样的空间显然是$O(NlogN)$的：$O(N+2\times \frac{N}{2}+4\times \frac{N}{4}+...)$
如果我们想求从$j$开始的下凸包中的最优转移，我们可以先定位到覆盖区间是$[j,n]$的节点集合$S$（集合大小是$logN$级的）
这样就顺利得到了多个分开的下凸包；在每个下凸包中二分地找（对于此下凸包）最优的转移，$dp[i]$取这些转移中$DP$值的$min$
为什么这样的是对的呢？因为$[j,n]$整体的最优转移$k$，一定是某段下凸包的最优转移
用反证法：若$k$不是某下凸包的最优转移，则存在一条边，不仅大于凸包中$k$为起点的边的斜率、又满足最优斜率的性质；那么这条边一定也出现在$[j,n]$整体的凸包中，则$k$不是整体的最优转移
这样一来，查询的问题就解决了，单次是$O((logN)^2)$的；接下来是在$dfs$过程中执行插入和删除
插入：进入某树节点时，我们对$i$所在的全部$logN$个区间全部插入$i$
删除：离开某树节点时，我们对$i$所在的全部$logN$个区间全部恢复插入$i$前的状态（把插入时右端弹出的点记录一下，恢复时直接赋回去就行了）
我们的做法假在恢复状态——一个“菊花”形状的树能让我们总体的恢复节点数达到$O(N^2)$！
好像很多用这种方法的人没有意识到....
（当然，想让左边$\frac{n}{2}$个点的斜率单调增也不容易...但卡掉还是挺可能的）
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std; typedef long long ll;
const ll INF=1LL<<;
const int N=; int n,sz=;
int fv[N];
ll sv[N],pv[N],qv[N],lv[N];
vector<int> v[N]; int stack[N];
ll sum[N],dp[N]; inline ll Calc(int i,int j)
{
return dp[j]+(sum[i]-sum[j])*pv[i]+qv[i];
} inline double Slope(int j,int k)
{
return (dp[j]-dp[k])/double(sum[j]-sum[k]);
} int arr[N*];
int l[N<<],r[N<<]; int rsave[N][];
int rcnt[N][];
int rear=;
int save[N*]; inline void Insert(int k,int x,int a,int b,int d,int layer)
{
if(a==b)
{
arr[++r[k]]=x;
return;
} rcnt[d][layer]=;
while(r[k]-l[k]> && Slope(arr[r[k]],arr[r[k]-])>=Slope(x,arr[r[k]]))
save[++rear]=arr[r[k]],rcnt[d][layer]++,r[k]--;
rsave[d][layer]=r[k];//
arr[++r[k]]=x; int mid=(a+b)>>;
if(d<=mid)
Insert(k<<,x,a,mid,d,layer+);
else
Insert(k<<|,x,mid+,b,d,layer+);
} inline void Recover(int k,int a,int b,int d,int layer)
{
if(a==b)
{
r[k]=l[k]-;
return;
} int mid=(a+b)>>;
if(d<=mid)
Recover(k<<,a,mid,d,layer+);
else
Recover(k<<|,mid+,b,d,layer+); r[k]=rsave[d][layer];
for(int i=;i<=rcnt[d][layer];i++)
arr[++r[k]]=save[rear--];
} inline void getDP(int k,int p,int a,int b,int cur)
{
if(a>=p)
{
int left=l[k],right=r[k],mid;
while(left<right)
{
mid=(left+right)>>;
if(Calc(cur,arr[mid+])<Calc(cur,arr[mid]))
left=mid+;
else
right=mid;
} if(left==right)
dp[cur]=min(dp[cur],Calc(cur,arr[left]));
return;
} int mid=(a+b)>>;
if(p<=mid)
getDP(k<<,p,a,mid,cur);
getDP(k<<|,p,mid+,b,cur);
} inline void dfs(int x,int d)
{
sum[x]=sum[fv[x]]+sv[x];
stack[d]=x; int left=,right=d-,mid;
while(left<right)
{
mid=(left+right)>>;
if(sum[x]-sum[stack[mid]]>lv[x])
left=mid+;
else
right=mid;
}
dp[x]=INF;
getDP(,left,,sz,x); Insert(,x,,sz,d,);
for(int i=;i<v[x].size();i++)
dfs(v[x][i],d+);
Recover(,,sz,d,);
} int main()
{
// freopen("testdata.in","r",stdin);
int T;
scanf("%d%d",&n,&T);
while(sz<n)
sz<<=;
for(int i=;i<=n;i++)
{
scanf("%d%lld%lld%lld%lld",&fv[i],&sv[i],&pv[i],&qv[i],&lv[i]);
v[fv[i]].push_back(i);
} for(int i=;i<=sz;i<<=)//
for(int j=;j<i;j++)
l[i+j]=r[i+j-]+,r[i+j]=l[i+j]+sz/i-;
for(int i=;i<(sz<<);i++)
r[i]=l[i]-; Insert(,,,sz,,);
for(int i=;i<v[].size();i++)
dfs(v[][i],); for(int i=;i<=n;i++)
printf("%lld\n",dp[i]);
return ;
}
（正解是树分治+斜率优化$DP$...还得啥时候再学一下orz）
暂时就把题目补到这里吧，以后遇到了有意思的题再放上来
牛客ACM 890J （$Wood\ Processing$）
这个写的真不熟...写的巨慢的主要原因还是dp式子一开始写错了
然后，用double比较的话一定要避免除$0$
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; struct Plank
{
int w,h;
Plank(int a=,int b=)
{
w=a,h=b;
}
}; typedef pair<int,int> pii;
typedef long long ll;
const int N=;
const int K=;
const ll INF=1LL<<;
const double eps=0.000001; int n,k;
Plank a[N]; inline bool cmp(Plank x,Plank y)
{
if(x.h!=y.h)
return x.h<y.h;
return x.w<y.w;
} int h[N];
ll sum[N],w[N]; ll dp[N][K];
int Q[N]; inline ll Calc(int i,int j,int k)
{
return dp[k][j-]+(sum[i]-sum[k])-(w[i]-w[k])*h[k+];
} inline ll Up(int i,int j)
{
return dp[j][i-]-sum[j]+w[j]*h[j+];
} inline double Slope(int i,int j,int k)
{
return (Up(i,j)-Up(i,k))/double(h[j+]-h[k+]);
} int main()
{
// freopen("input.txt","r",stdin);
// freopen("my.txt","w",stdout);
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].h); sort(a+,a+n+,cmp); int tot=;
for(int i=;i<=n;i)
{
tot++;
sum[tot]=sum[tot-];
w[tot]=w[tot-];
h[tot]=a[i].h; int j=i;
while(j<=n && a[j].h==a[i].h)
{
sum[tot]+=ll(a[j].w)*a[j].h;
w[tot]+=a[j].w;
j++;
}
i=j;
} n=tot;
for(int i=;i<=n;i++)
for(int j=;j<=k;j++)
dp[i][j]=INF; for(int i=;i<=n;i++)
dp[i][]=sum[i]-w[i]*h[]; for(int i=;i<=k;i++)
{
int p=,sz=;
Q[]=;
for(int j=;j<=n;j++)
{
while(p<sz && Calc(j,i,Q[p])+eps>Calc(j,i,Q[p+]))
p++;
dp[j][i]=Calc(j,i,Q[p]); while(sz> && Slope(i,Q[sz],Q[sz-])+eps>Slope(i,j,Q[sz]))
sz--;
Q[++sz]=j;
if(p>sz)
p=sz;
}
} printf("%lld\n",dp[n][k]);
return ;
}
（完）