2 shunfurh shunfurh 于 2017.01.08 11:49 提问

Print Article

Problem Description
Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost

M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

Input
There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

Output
A single number, meaning the mininum cost to print the article.

Sample Input
5 5 5 9 5 7 5

Sample Output
230

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.08 11:48
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
HDU 3507 Print Article(斜率优化DP)
题目链接 基础的斜率优化DP 参考代码: #include #include #include #include using namespace std; const int maxn= 500050; int A[maxn] , dp[maxn] ,sum[maxn], M; int myque[maxn],head,tail,N; #define Y(i) (dp[i]+su
HDU 3507 Print Article
#include #include #define maxn 500005 #define inf 0xffffff int dp[maxn]; int Q[maxn]; int sum[maxn]; int get1(int i) { return dp[i]+sum[i]*sum[i]; } int get2(int i,int j) { return sum[i]
hdu3507 Print Article
Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 7513    Accepted Submission(s): 2341 Problem Description Zero has an old printer th
HDU3507 Print Article
HDU3507 Print Article.关于程序算法艺术与实践更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.
[HDU 3507] Print Article
Problem Link    这题应该可以算是斜率优化dpdp的入门题了,为了巩固斜率优化dpdp的方法,我特此写一篇题解表明我是真懂了。Description    给定nn和mm以及一个含nn个元素的序列,要求依次取完所有的数,每次取一段连续的数的花费是,这一段中所有数之和的平方加上mm,求取完所有数的最小花费。Solution    这道题显然是道dpdp题,而且O(n2)O(n^2)的dp
【动态规划】print article
Problem Description Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certain
【HDU 3507】 Print Article
很标准的一道DP题+斜率优化 因为规定了是连续子串,所以必然满足wu
Print Article[HDU 3507]
Problem DescriptionZero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly
hdoj 3507 Print Article
我的第一道斜率优化dp。   首先,O(n^2)复杂度的dp是很容易想到的。现在我们需要用斜率优化把每次转移的复杂度优化到O(1)。考虑从dp(a)和dp(b)转移到dp(i),若从dp(a)转移要优,则有dp(a)+(sum(i)-sum(a))^2+M   于是可以得到这样的关系:(Y(a)-Y(b))/(X(a)-X(b)) 由a转移较优;(Y(a)-Y(b))/(X(a)-X(b))>
hdu-3507 Print Article
题意: 给出n,m,求在n个数中分成任意段; 每段的花销是(sigma(a[l],a[r])+m)^2; 求这个最小值; 题解: 斜率优化入门题; 然而入门并不是这么容易的(笑); 我们可以很容易的得到dp方程; f[i]=f[j]+(s[i]-s[j]+m)^2 其中s[x]表示x的前缀和,0 O(n^2)超时; 我们把平方打开可得; f[i] = f[j]+(s