题解 P6047 【丝之割】

· · 题解

真的是非常 amazing 的一道斜率优化DP题啊。

前两天学了斜率优化，然后就想着找几道题做一做，苦于斜率优化它就没有几道蓝以下的题，所以第一道就被卡住了，当然事后发现是一个SB错误。对斜率优化还没有什么了解的可以看我的博客，如果还有闲心，可以看看我原来写的乱搞，大概展现了我做这道题整个的心理变化？然后最后稍微总结一下斜率优化 DP 里面的一些细节，还有不能太确定的。

观察题面，它要求我们破坏几个二元组，其中非常特殊的一点是，必须从左到右穿过，才能破坏这个二元组，也就是：对于一次切割 (i,j)，你会切掉的弦包括 (u,v)u>i,j<v。那么于是我们能够得到，对于一两个二元组 (i,j),(u,v)，如果 i>u,j<v 那么二元组 (i,j) 是无用的，因为切掉第二个二元组的切割一定能切掉第一个二元组。然后我们再发现，这个东西事实上等于是不允许有用的二元组之间存在交叉。看一下图片：

在这个情况中，按上端点排序从左到右第二根弦是无用的。那么，最后去掉所有无用的二元组之后，我们得到了类似于这种情况的结果：

既然不允许交叉，那么我们有随着 u 的递增，所有的弦的 v 也是递增的这一性质。那么这样的话事情就非常的明朗了，我们定义状态 dp_i 是把前 i 根弦全部切掉的最小代价。定义 mina_{i,j} 是 i 与 j （按连接点编号）之间的 a 的最小值，minb_{i,j} 的定义类似，那么我们有状态转移方程：

dp_{i}=\min_{j<i}\{ dp_j+mina_{1,u_{j+1}-1}\times minb_{v_i+1,n}\}

然后我们就能把斜率优化的板子套上去了，点的坐标是 (-mina_{1,u_{j+1}-1},dp_j) ，斜率是 minb_{v_i+1,n}，具有单调性质，可以使用单调队列维护一个下凸壳。某个【数据删除】跟我说了包括“这道题没有单调性质，必须要单调栈内二分”，“从队头入点从队尾出点才行”，“这道题的状态转移方程是 dp_{i}=\min\limits_{j<i}\{ dp_j+mina_{u_j,u_{j+1}-1}\times minb_{v_i+1,n}\}”，“斜率有可能是负的，点有可能在第二象限，所以维护一个下凸壳炸掉了”等等的一系列睿智言论，某种程度上他就是导致我卡这么久的罪魁祸首。那么既然有了点的坐标有了斜率就可以直接套斜率优化的板子上去了，接下来是代码。

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[300005],b[300005],u[300005],v[300005];
long long gt[300005],st[300005],deq[300005],s=1,t=1;
long long dp[300005];
struct node{
    long long u,v;
    friend bool operator<(node a,node b){
        if(a.u==b.u)
            return a.v>b.v;
        return a.u<b.u;
    }
}cts[300005];
double slope(int x,int y){
    if(st[u[x+1]-1]==st[u[y+1]-1])
        return 1e18;
    return 1.0*(dp[x]-dp[y])/(st[u[y+1]-1]-st[u[x+1]-1]);
}
int main(){
    // freopen("P6047_6.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=m;i++)
        cin>>cts[i].u>>cts[i].v;
    sort(cts+1,cts+m+1);
    int TOT=m;
    m=0;
    for(int i=1,mx=0;i<=TOT;i++){
        if(cts[i].v>mx){
            u[++m]=cts[i].u;
            v[m]=cts[i].v;
        }
        mx=max(1ll*mx,v[m]);
    }
    gt[n+1]=1e18;
    st[0]=1e18;
    u[0]=1;
    for(int i=n;i>=0;i--)
        gt[i]=min(gt[i+1],b[i]);
    for(int i=1;i<=n;i++)
        st[i]=min(st[i-1],a[i]);
    for(int i=1;i<=m;i++){
        while(s<t&&slope(deq[s],deq[s+1])<gt[v[i]+1]){
            s++;
        }
        dp[i]=dp[deq[s]]+st[u[deq[s]+1]-1]*gt[v[i]+1];
        while(s<t&&slope(deq[t-1],deq[t])>slope(deq[t],i)){
            t--;
        }
        deq[++t]=i;
    }
    cout<<dp[m];
}

然后是比较简短的总结，包括一些常见的误区。首先，因为斜率优化它的模板柿子是 b=y-kx，所以记得 k 和 x 里面其中一个要搞成负的。第二个，使用单调队列的条件是斜率满足单调性质而不是点满足单调性质，如果不满足单调性质可以换用单调栈内二分，复杂度多一个 log。第三个，由于两个点的 x 坐标有可能相同所以需要特判成 inf，如果不特判会变成 -inf。

没了，就这样。