[CEOI2004] 锯木厂选址 - 斜率优化dp

Description

从山顶上到山底下沿着一条直线种植了 n 棵老树。树被砍倒后要运送到锯木厂。木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。每公斤木材每米需要一分钱。

Solution

设 \(s_i\) 表示前 \(i\) 棵树的重量之和，\(d_i\) 表示从第 \(i\) 棵树到山脚的距离，那么 \(f_i = \min_j (tot - s_j d_j - (s_i - s_j) d_i)\)，相当于我们枚举了较低的一个锯木厂的位置 \(i\)，要对较高的一个位置 \(j\) 取 \(\min\)。

对于 \(j\)，\(x\) 比 \(y\) 优，当且仅当 \(\frac {s_x d_x - s_y d_y} {s_x - s_y} > d_i\)。

于是维护一个斜率单调递减的上凸包，斜率即 \(\frac {s_x d_x - s_y d_y} {s_x - s_y}\)，显然我们希望找到一个 \(x\) 使得 \(x+1\) 不比 \(x\) 优，那么这时 \(x \to x+1\) 的斜率应该要小于 \(d_i\)。

因此我们求出队首两个点的斜率，如果大于 \(d_i\) 就弹出，那么队首就是答案。

至于队尾，由于每次压入的时候，要考虑到斜率的单调递减，因此如果最后一段的斜率小于即将新加入的一段的斜率，那么就需要在队尾进行删除。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n,d[N],w[N],s[N],c[N],f[N],tot,q[N],head=1,tail=0,ans=1e18;

double slope(int x,int y)
{
    return 1.0*(s[x]*d[x]-s[y]*d[y])/(s[x]-s[y]+1e-8);
}

int calc(int i,int j)
{
    return tot-s[j]*d[j]-(s[i]-s[j])*d[i];
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>d[i];
    
    for(int i=1;i<=n;i++) s[i]=s[i-1]+w[i];
    for(int i=n;i>=1;i--) d[i]+=d[i+1];

    for(int i=1;i<=n;i++) tot+=d[i]*w[i];

    for(int i=1;i<=n;i++)
    {
        while(head<tail && slope(q[tail],q[tail-1])<slope(q[tail],i)) --tail;
        q[++tail]=i;
        while(head<tail && slope(q[head],q[head+1])>d[i]) ++head;
        f[i]=calc(i,q[head]);
        ans=min(ans,f[i]);
    }

    cout<<ans<<endl;
}

[CEOI2004] 锯木厂选址 - 斜率优化dp

原文：https://www.cnblogs.com/mollnn/p/14027515.html