问题2152--打印文章（HDU3507）

2152: 打印文章（HDU3507）

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

小明要打印一篇有N 个单词的文章。每个单词i 都有一个打印成k 本Ci 。在一行中打印k 个单词要花费的成本为，其中M 是常量。他想知道打印文章的最小成本。

输入

输入包含多个测试用例。每个测试用例的第1行都包含两个数字N 和M （0≤N ≤500000，0≤M ≤1000）。在接下来的2～N +1行中有N 个数字，表示N 个单词的打印成本。

输出

单行输出打印文章的最小成本。

样例输入 Copy 

5 5
5
9
5
7
5

样例输出 Copy 

230

来源/分类

动态规划算法 单调队列 斜率优化 
[提交] [状态]