博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ 1010】 [HNOI2008]玩具装箱toy
阅读量:5842 次
发布时间:2019-06-18

本文共 1518 字,大约阅读时间需要 5 分钟。

Description

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。但他希望费用最小.

Input

第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1
 
DP方程显然 f[i]=min(f[j]+i-j+h[i]-h[j]-L-1)^2//这里[I,J]表示从i到j+1这段区间
目前我只会用斜率优化做,论代换的重要性
我的方程式五个式子相加再平方化出来的。。。不想在这写了,太恶心了
黄学长是将h[i]+i,h[j]+j,L-1看成了一个整体,瞬间好算了好多

懒得写了。。。上代码了,有时间再填坑、、、

1 #include
2 #define ll long long 3 const int N=50010; 4 int c[N],n,L,q[N]; 5 ll h[N],ans,f[N],m; 6 int l=0,r=0; 7 ll sqr(ll x){
return x*x;} 8 9 double calc(int k,int j){10 return (f[j]-f[k]+j*j-k*k+sqr(h[j])-sqr(h[k])+2*11 (j*h[j]-k*h[k]+(j+h[j])*m-(k+h[k])*m))/((j-k+h[j]-h[k])+0.0);12 }13 14 void dp(){15 for (int i=1;i<=n;i++){16 double mid=calc(q[l],q[l+1]);17 while(l
<=2*(i+h[i])) l++;18 f[i]=f[q[l]]+sqr((i-q[l]+h[i]-h[q[l]]-L-1));19 while(l
calc(q[r],i)) r--;20 q[++r]=i;21 }22 }23 24 int main(){25 scanf("%d%d",&n,&L);m=L+1;26 for (int i=1;i<=n;i++){27 scanf("%d",&c[i]);28 h[i]=h[i-1]+c[i];29 }30 dp();31 printf("%lld",f[n]);32 }

m一定要是ll类型的,一定!!!

转载于:https://www.cnblogs.com/wuminyan/p/5194205.html

你可能感兴趣的文章
OpenSSL漏洞凶猛来袭 慧眼恶意代码监测应对有方
查看>>
C语言 喝汽水问题
查看>>
LINUX中搭建DNS服务器,实现正向、反向以及访问不同DNS解析
查看>>
SCCM2012 R2实战系列之十:解决WDS服务无法启动问题(错误1067:进程意外终止)...
查看>>
ubuntu 下安装 mysql
查看>>
关于k-means聚类算法的matlab实现
查看>>
Git分支2
查看>>
一键安装Gitlab后的备份、迁移与恢复
查看>>
因为本人工作繁忙,精力有限,本博客停止更新。有兴趣的博友可以关注我在CSDN上的主博客...
查看>>
SQL server查看触发器是否被禁用
查看>>
[C++基础]在构造函数内部调用构造函数
查看>>
跟随我在oracle学习php(8)
查看>>
Spring 3.1.0 Hibernate 3.0 Eclipse Spring WEB例子
查看>>
UVA-10212 The Last Non-zero Digit. 分解质因子+容斥定理
查看>>
求两个集合的交集,并集,差集
查看>>
Kotlin的语法糖(一)基础篇
查看>>
OkHttp源码分析
查看>>
让你的app体验更丝滑的11种方法!冲击手机应用榜单Top3指日可待
查看>>
windows kernel exploitation基础教程
查看>>
NS_OPTIONS枚举的用法
查看>>