| 题目名称 | 1791. [国家集训队2012]积木 |
|---|---|
| 输入输出 | nt2012_brick.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1500 ms (1.5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-11-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：3， 通过率：33.33% | ||||
 cstdio |
100 | 1.102 s | 40.16 MiB | C++ |
|
cstdio |
80 | 1.189 s | 42.28 MiB | C++ |
|
cstdio |
15 | 1.086 s | 42.28 MiB | C++ |
| 关于 积木 的近10条评论(全部评论) |
|---|
积木(沈添笑)
时间限制：1.5s 内存限制：256.0MB
【问题描述】
搭积木是xx最喜欢的游戏之一。xx有n块高低不同的积木，她将它们排成一列。xx希望积木看起来尽可能的整齐，她将相邻两块积木高度之差的绝对值之和乘上系数c定义为积木序列的混乱值，显然，混乱值越小越好。xx可以通过调整积木的高度使其混乱值变小，她可以花费t^2的代价，往某块积木上再搭一块高为t(t为任意自然数)的积木，在同一块积木上只能搭一次。
xx想考考你，混乱值与花费之和的最小值是多少呢？
xx想考考你，混乱值与花费之和的最小值是多少呢？
【输入格式】
输入的第一行包含两个整数n, c。接下来n行，第i行一个整数hi，代表第i块积木的高度。
【输出格式】
输出一个整数，代表最小花费。
【样例输入】
4 1
1
2
1
3
1
2
1
3
【样例输出】
3
【数据规模和约定】
20%的数据满足：n、h≤100
40%的数据满足：n、h≤1000
60%的数据满足：n≤1000
80%的数据满足：n≤100000
100%的数据满足：1≤n、h、c≤1000000
40%的数据满足：n、h≤1000
60%的数据满足：n≤1000
80%的数据满足：n≤100000
100%的数据满足：1≤n、h、c≤1000000