Alioth_ 的博客

Alioth_ 的博客

斜率优化

posted on 2018-12-28 15:41:11 | under 知识点 |

一.条件:

形如

f(i)=max/min{f(j)+val(i,j)}

其中$val(i,j)$是关于$i,j$的乘积项

二.拆状态转移方程

决策(如$a[j]$)作为自变量$x$

如果需要满足某些特殊条件 则需要开多维队列(在每个决策上开一个队列(如关于$a[j].y$))强制使这个决策作为定值 再处理另一个决策 如$P4056$火星藏宝图

#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$值不单调

不能在队列里删决策 用二分查找找最优决策

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]货币兑换

#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]);
}