P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.
【bzoj1010】【HNOI2008】【玩具装箱toy】【斜率优化】
发布日期:2021-11-16 15:38:16
浏览次数:16
分类:技术文章
本文共 1275 字,大约阅读时间需要 4 分钟。
Description
Input
第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
Output
输出最小费用
Sample Input
5 4
3
4
2
1
4
3
4
2
1
4
Sample Output
1
题解:斜率优化模板题。
代码:
#include#include #include using namespace std;const int N=50100;long long sum[N],L,f[N];int l[1000000],n;long long pow(long long x){return x*x;}long long S(int x,int y){return sum[x]-sum[y];}long long G(int x,int y){return f[x]-f[y]+pow(sum[x]+L)-pow(sum[y]+L);}long long work(int x,int y){return (G(x,y)*1.0)/(S(x,y)*2.0);}int main(){ int i,j,h=1,t=1; scanf("%d%lld",&n,&L); L+=1; for(i=1;i<=n;++i){ scanf("%lld",&sum[i]); sum[i]+=sum[i-1]; } for(i=1;i<=n;++i) sum[i]+=(long long)i; l[1]=0; for(i=1;i<=n;++i){ while(h =work(l[h+1],l[h])) h+=1; f[i]=f[l[h]]+pow(sum[i]-sum[l[h]]-L); while(h <=work(l[t],l[t-1])) t-=1; t+=1;l[t]=i; } printf("%lld\n",f[n]);}
转载地址:https://blog.csdn.net/sunshinezff/article/details/50965781 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年03月29日 05时13分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C++(标准库):51---并发之(原子操作:atomic)
2019-04-26
一文带你入门了解“零之禅“消息队列ZeroMQ
2019-04-26
手把手教学,以源码方式在Linux下编译安装消息队列ZeroMQ
2019-04-26
ZeroMQ文档白嫖:ZeroMQ的版本变更、zmq_version()函数
2019-04-26
独树一帜,带你了解ZeroMQ对字符串处理
2019-04-26
ZeroMQ文档白嫖:千字详解ZeroMQ的ctx上下文
2019-04-26
Linux下安装Redis数据库
2019-04-26
使用源码包编译安装Nginx
2019-04-26
服务/软件管理:50---Linux更换镜像源
2019-04-26
C语言操作Redis(hiredis库)
2019-04-26
Linux(程序设计):65---同步HTTP请求、异步HTTP请求
2019-04-26
C++(数据结构与算法):64---布隆过滤器(Bloom Filter)
2019-04-26
Linux(程序设计):24---无锁CAS(附无锁队列的实现)
2019-04-26
Linux(程序设计):66---简略版的线程池设计
2019-04-26