斜率优化
Alioth_
2018-12-28 15:41:11
### 一.条件：
形如
``f(i)=max/min{f(j)+val(i,j)}``
其中$val(i,j)$是关于$i,j$的乘积项
### 二.拆状态转移方程
决策（如$a[j]$）作为自变量$x$
如果需要满足某些特殊条件 则需要开多维队列（在每个决策上开一个队列（如关于$a[j].y$））强制使这个决策作为定值 再处理另一个决策 如[$P4056$火星藏宝图](https://www.luogu.org/problemnew/show/P4056#sub)
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200000+10;
struct point{
int x,y,v,id;
}a[maxn];
bool cmp(point a,point b)
{
return a.id<b.id;
}
int n,m;
int f[maxn],q[1010][maxn],l[maxn],r[maxn];
double calc(int i,int j)
{
return 1.0*(f[i]-a[i].x*a[i].x-f[j]+a[j].x*a[j].x)/(a[i].x-a[j].x);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].v);
a[i].id=(a[i].x-1)*m+a[i].y;
}
sort(a+1,a+1+n,cmp);
memset(f,0xcf,sizeof(f));
f[1]=a[1].v;
q[1][++r[1]]=1;
//此题有三个关于决策的变量 一个作为x 一个作为y 还有一个无法处理 要把它当成定值
//所以就要建m个（关于第三个变量a[j].y）队列 每次用两重循环在前面队列里找
//找到的答案在当前队列中更新就行了
for(int i=2;i<=n;i++)
{
for(int j=1;j<=a[i].y;j++)
{
while(l[j]<r[j]&&calc(q[j][l[j]],q[j][l[j]+1])>-2*a[i].x)l[j]++;
f[i]=max(f[i],f[q[j][l[j]]]+a[i].v-(a[i].y-j)*(a[i].y-j)-(a[q[j][l[j]]].x-a[i].x)*(a[q[j][l[j]]].x-a[i].x));
}
int j=a[i].y;
while(l[j]<r[j]&&calc(q[j][r[j]],q[j][r[j]-1])<calc(i,q[j][r[j]]))r[j]--;
q[j][++r[j]]=i;
}
cout<<f[n];
}
```
与决策$j$有关的项(如$f[j]$)作为因变量$y$
$k$值为关于阶段$i$的定值 其他部分作为截距（要包含要求的$f[i]$）
### 三.求$max$还是$min$
$max$时维护上凸包 $min$时维护下凸包
### 四.单调性
#### $1.k$值单调
选决策时直接在队头删决策然后直接选$q[l]$
#### $2.k$值不单调
不能在队列里删决策 用二分查找找最优决策
```cpp
int binary_search(int k)
{
if(l==r)return q[l];
int L=l,R=r;
while(L<R)
{
int mid=(L+R)>>1;
if((f[q[mid+1]]-f[q[mid]])<=k*(sumc[q[mid+1]]-sumc[q[mid]])) L=mid+1;
else R=mid;
}
return q[L];
}
```
#### $3.x$值不单调
调整方程把$x$作为$k$ 再用二分查找
或某些情况下可以倒序$dp$
#### $4.k\ x$均不单调
$splay$或$CDQ$分治
$CDQ:$
先按照每个决策的$k$排序 **这时决策是线 只用记录$k$值**
分治内部按照时间分成左右两侧（保证在左右侧内$k$值均单调）
然后$cdq(l,mid)$因为要按时间计算$f$计算好的$x$值是单调的
把左边的决策当作点插入队列，把右边的决策当做线去截每一个点 答案记录在$dp$数组中 这时候保证右边$k$单调 左边$x$单调（！）
$cdq(mid+1,r)$
返回时把$l$到$r$按照$x$排序（这样可以保证计算点时$x$值是单调的）
**到$l==r$时 决策由线转化为了点 用$dp$数组求出$x$和$y$ 然后再返回 **
与普通$CDQ$不同的是，这个处理左侧对右侧的影响时要求左侧$x$有序，不要求$k$有序，右侧$k$有序，但不要求$x$有序（左侧只插入 作为点 右侧只计算，作为线）。所以需要在处理影响之前先计算左边，返回时排好$x$，这时队列中保存了左侧点的所有决策，计算完影响后再分治右边。
而普通的$CDQ$要在内部进行二维偏序，不要求剩余两维的单调性，所以可以先递归，最后再合并。
注意 决策是点 需要求解的是一条$k$值固定的直线的截距 要去截决策点 截完要插入新的决策点i **插入和找决策点是两个相互独立的过程** 所以$x$不单调时要动态的在点集里插入新的决策点 **可以理解为点和线是一个决策的两种实现形式 插入时是点 计算决策时是线
**算$k$时若$k$不存在 应返回$inf$或$-inf$**
[$P4027$ [NOI2007]货币兑换](<https://www.luogu.org/problemnew/show/P4027>)
```cpp
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-9
using namespace std;
const int maxn=100010;
int n,s[maxn];//单调队列由于不用删除变成单调栈
double dp[maxn];
struct Q{
double k,a,b,x,y,r;
int id;
}q[maxn],tmp[maxn];
inline bool cmp1(Q aa,Q bb){
return aa.k<bb.k;
}
inline bool cmp2(Q aa,Q bb){
return aa.x<bb.x;
}
double slope(int i,int j){
if(fabs(q[i].x-q[j].x)<eps)return inf;//求min时斜率不存在返回inf
return (double)(q[i].y-q[j].y)/(q[i].x-q[j].x);
}
void CDQ(int l,int r)
{
if(l==r){
dp[l]=max(dp[l],dp[l-1]);
q[l].y=dp[l]/(q[l].r*q[l].a+q[l].b);
q[l].x=q[l].y*q[l].r;
return ;
}
int mid=l+r>>1;
int p1=l-1,p2=mid,top=0;
for(int i=l;i<=r;i++)
if(q[i].id<=mid)tmp[++p1]=q[i];
else tmp[++p2]=q[i];
for(int i=l;i<=r;i++)q[i]=tmp[i];//左右两边按照时间排序
CDQ(l,mid);//处理左边 之后左边的线变成点
for(int i=l;i<=mid;i++)//斜率递减 插入左边的点
{
while(top>=2&&slope(s[top],i)+eps>slope(s[top],s[top-1]))top--;
s[++top]=i;
}
for(int i=mid+1;i<=r;i++)//计算右边的线
{
while(top>=2&&q[i].k+eps>=slope(s[top],s[top-1]))top--;
int j=s[top];
dp[q[i].id]=max(dp[q[i].id],q[j].x*q[i].a+q[j].y*q[i].b);
}
CDQ(mid+1,r);
sort(q+l,q+r+1,cmp2);
}
int main()
{
scanf("%d%lf",&n,&dp[0]);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].r);
q[i].k=-q[i].a/q[i].b;
q[i].id=i;
}
sort(q+1,q+1+n,cmp1);
CDQ(1,n);
printf("%.3lf",dp[n]);
}
```