斜率优化DP P4360【锯木厂选址】

分析：

用sumw[i]记录∑ij=1w[j]∑j=1iw[j]维护前缀和

用sumd[i]记录∑i−1j=1d[j]∑j=1i−1d[j]维护前缀和

Cost[i]表示将第一个锯木厂建在i的位置时，1~i第一段的木材运到i的费用：

Cost[i]=Cost[i-1]+sumw[i-1]*d[i-1]

接着就可以用列出状态转移方程，设f[i]表示第二个锯木厂建在i时的费用

f[i]=min{ Cost[j]- sumw[j] (sumd[i]-sumd[j])- sumw[i] (sumd[n+1]-sumd[i]) }

令 y=sumw[j]*sumd[j] ，x=sumw[j] ，k=sumd[i]

维护下凸包，斜率优化乱搞即可。

下面是本蒟蒻的代码：

#include<bits/stdc++.h>
#define INF 0x7ffffffffff
using namespace std;
long long n,sumw[50005],sumd[50005],w[50005],d[50005],c[50005],q[50005],f[50005],ans=INF;
long double find(long long j,long long k){//计算斜率
    return (double)(sumw[k]*sumd[k]-sumw[j]*sumd[j])/(sumw[k]-sumw[j]);
}
int main() {
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)scanf("%lld%lld",&w[i],&d[i]);
    for(long long i=1;i<=n+1;i++) {
        sumw[i]=sumw[i-1]+w[i];//求出w的前缀和
        sumd[i]=sumd[i-1]+d[i-1];//求出d的前缀和
        c[i]=c[i-1]+sumw[i-1]*d[i-1];//c[i]表示把第一个锯木厂设在i，第一段木材运到i的总费用
    }
    long long l=1,r=1;
    q[1]=1;f[1]=0;
    for(long long i=2;i<=n;i++) {
        while(l<r&&find(q[l],q[l+1])<=sumd[i])l++;//维护队首（删除非最优决策）
        f[i]=sumw[q[l]]*sumd[q[l]]-sumd[i]*sumw[q[l]]+c[n+1]-sumw[i]*(sumd[n+1]-sumd[i]);
        while(l<r&&find(q[r-1],q[r])>=find(q[r],i))r--;//维护队尾（维护下凸包性质）
        q[++r]=i;//入队
        ans=min(ans,f[i]);
    }
    printf("%lld",ans);
    return 0;
}

小提示：不开long long 见祖宗