首页 / 更多教程 / [题解]luogu_P2120_仓库建设（基础斜率优化

[题解]luogu_P2120_仓库建设（基础斜率优化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[题解]luogu_P2120_仓库建设（基础斜率优化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1423字，纯文字阅读大概需要3分钟。

内容图文

过程：

$f[i]=min(f[j]+\sum_{k=j+1}^{i}p_{k}*(x_{i}-x_{k}))+c[i]$

令$sum[i]=\sum_{j=1}^{i}p_{k},sumx[i]=\sum_{j=1}^{i}p_{k}*x_{k}$

$f[i]=min(f[j]+(sum[i]-sum[j])*x[i]-(sumx[i]-sumx[j]))+c[i]$

若$j$比$k$优

$f[j]+(sum[i]-sum[j])*x[i]-(sumx[i]-sumx[j])<=f[k]+(sum[i]-sum[k])*x[i]-(sumx[i]-sumx[k])$

$f[j]-f[k]<=(sum[j]-sum[k])*x[i]+sumx[k]-sumx[j]$

$\frac{f[j]-f[k]+sumx[j]-sumx[k]}{sum[j]-sum[k]}<=x[i]$

（未过BZOJ）

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
usingnamespace std;
constint maxn=1e6+9;
int n,x[maxn],p[maxn],c[maxn];
ll s[maxn],sx[maxn],f[maxn];
//s[i]=sumpi sx[i]=sum(pi*xi)
//f[j]-f[k]+sx[i]-sx[k]<=x[i]*(s[j]-s[k])int q[maxn];
inline ll up(int j,int k){
    return f[j]-f[k]+sx[j]-sx[k];
}
inline ll down(int j,int k){
    return s[j]-s[k];
}
inline ll dp(int i,int j){
    return f[j]+(s[i]-s[j])*x[i]-(sx[i]-sx[j])+c[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d%d",&x[i],&p[i],&c[i]),s[i]=s[i-1]+p[i],sx[i]=sx[i-1]+(ll)p[i]*x[i];
    int head=1,tail=1;
    for(int i=1;i<=n;i++){
        while(head<tail && up(q[head+1],q[head])<=x[i]*down(q[head+1],q[head]))head++;
        f[i]=dp(i,q[head]);
        while(head<tail && up(i,q[tail])*down(q[tail],q[tail-1])<=up(q[tail],q[tail-1])*down(i,q[tail]))tail--;
        q[++tail]=i;
    }
    printf("%d",f[n]);
    
}

 

原文：https://www.cnblogs.com/superminivan/p/11299576.html

内容总结

以上是互联网集市为您收集整理的[题解]luogu_P2120_仓库建设（基础斜率优化全部内容，希望文章能够帮你解决[题解]luogu_P2120_仓库建设（基础斜率优化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1271972.html

来源：【匿名】