| 题目名称 | 1330. [HNOI 2008]玩具装箱toy |
|---|---|
| 输入输出 | bzoj_1010.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 QhelDIV
于2013-03-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：201， 提交：416， 通过率：48.32% | ||||
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_Queuer |
100 | 0.000 s | 0.14 MiB | C++ |
 Hzoi_Yniverse |
100 | 0.000 s | 0.73 MiB | C++ |
 Pine |
100 | 0.000 s | 1.02 MiB | C++ |
|
op_组撒头屯 |
100 | 0.000 s | 1.41 MiB | C++ |
 Youngsc |
100 | 0.005 s | 0.76 MiB | C++ |
 Respawn |
100 | 0.018 s | 0.44 MiB | C++ |
|
Hzoi_Yniverse |
100 | 0.027 s | 0.29 MiB | C++ |
 new ioer |
100 | 0.035 s | 2.48 MiB | C |
 Asm.Def |
100 | 0.051 s | 1.63 MiB | C++ |
| 关于 玩具装箱toy 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
刚进前500QAQ
 李俊辉
2019-08-22 21:47
17楼
| ||||
|
整天就知道决策单调性，我没救了= =
| ||||
|
一开始head初始化成0了，没发现，又推了一遍式子，恶心得要死要活的
 不过斜率优化1A，爽   Hzoi_chairman
2016-11-11 17:59
15楼
| ||||
|
5000积分留念！
| ||||
|
这个宏定义写的自己看着都醉。
| ||||
|
第一发斜率优化
 _Itachi
2016-09-13 15:28
12楼
| ||||
|
今天运气不错
| ||||
|
| ||||
|
回复 @<蒟蒻>刚铎 :
 zys
2015-08-06 17:59
9楼
| ||||
|
各种错误，while后面写了分号看不见...0.00.0
 0
2015-08-02 07:14
8楼
| ||||
AntiLeaf
FoolMike
安呐一条小咸鱼。
mikumikumi【题目描述】
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一维，再放到一种特殊的一维容器中。
P教授有编号为$1,2,\cdots,n$的$n$件玩具，第$i$件玩具经过压缩后变成一维长度为$c_i$。为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个
单位长度的填充物，形式地说如果将第$i$件玩具到第$j$个玩具放到一个容器中，那么容器的长度将为
$$x=j-i+\sum_{i\leq k \leq j} c_k$$
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为$x$,其制作费用为$(x-L)^2$.其中$L$是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过$L$。但他希望费用最小.
【输入格式】
第一行输入两个整数$n, L$。
接下来$n$行每行一个整数表示$c_i$。
【输出格式】
一行，一个整数表示最小费用。
【输入样例】
5 4 3 4 2 1 4
【输出样例】
1
【数据范围与约定】
$1\leq n\leq 50000,1\leq L,c_i\leq 10^7$