斜率优化DP
QWQ
upd：这里是yyb的更新，今天是2019.3.18的晚上。
我觉我的这篇文章就是在扯蛋，所以到这里看斜率优化把QwQ。
题外话
考试的时候被这个玩意弄得瑟瑟发抖
大概是yybGG的Day4
小蒟蒻表示根本不会做…..
然后自己默默地搞了一下斜率优化
这里算是开始吗??
其实我讲的会非常非常非常简单,,,而且绝对没有一张图(因为我绘图水平太菜)
貌似没太多友善的题目可以用来搞….算了
虚一点,缥缈一点的来说吧….
其实我就是写给自己看的…
对于某一类DP方程形如:(当然max也可以)
\[f[i]=min(f[j]+g(i,j))
\]
其中\(g(i,j)\)
是一个只和i于j相关的函数
我们知道
转移一定是从某个位置转移过来了,其他位置的转移一定不会比这个位置好
所以,不妨设从j位置转移过来,另外一个奇怪的位置从k转一个过来
于是有:
\[f[j]+g(i,j)<f[k]+g(i,k)
\]
接下来再假设一步
我们假设\(g(i,j)=h(i)t(j)\)
其中 \(h(i)\)和\(t(j)\)是只和i与j有关的函数
那么不等式变为
\[f[j]+h(i)t(j)<f[k]+h(i)t(k)
\]
移项得
\[h(i)(t(j)-t(k))<f[k]-f[j]
\]
\[h(i)<\frac{f[k]-f[j]}{t(j)-t(k)}
\]
这个时候就看到右边的东西没有???
但是要记住，除过去可能会要变号
这玩意就可以视作一个斜率啦
但是,这个玩意有了不能够直接用嗷
只有当满足单调的时候才能够用斜率优化
当且仅当\(h(i)、f[i]、t(i)\)
都要满足单调的时候才能够用(根据取max或min,符号等单调性有所不同)
这个时候,利用单调队列维护一个凸包就可以啦
具体的类似代码如下:
for(int i=1;i<=n;++i)
{
while(head<tail&&count(Q[head],Q[head+1])<=h[i])Head++;
int get=Q[head];
f[i]=f[get]+Calc(i,get);
while(head<tail&&count(Q[tail-1],Q[tail])>=count(Q[tail],i))tail--;
Q[++tail]=i;
}
这是一份比较伪的代码
第一个while循环,目的是弹出队列头位置的不合法的状态(因为\(h(i)\)的值在变化)
中间的两句话是转移,可以直接利用斜率优化\(O(1)\)转移
后面那个while循环目的是维护单调性,当前的节点如果放进来会破坏队尾的单调性,所以要进行调整
最后一个是加入队尾,继续进行操作
这样子的话就可以维护斜率进行斜率优化啦
接下来是几道题目
有待补充
