hdu 3507 Print Article(斜率优化dp)

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
题意:一个长度为n的序列,让你划分成任意数目的连续段。每一段连续段的代价是.求这n个数的序列的最小价值。
斜率优化的入门题,但是也推了好久。
首先一个很明显的dp递推式:
,sum数组是前缀和。
但是这个是O(n^2),TLE。所以接着挖掘性质。
假设,假设选择j比k优。
那么就得到这样一个式子:
左右移项合并同类项后就是这个样子了:
因为,所以.我们把,视为,视为,依次类推。
那么上面的式子就变成了:,这就相当于k点到j点的斜率嘛。设k到j的斜率为
那么上面最终的式子是长这样的:,也就是如果两个决策点间的斜率满足这样的关系的话,我们就可以舍弃k点。
现在假设,如果,若,那么b比c优,a比b优。所以b可以被舍弃。如果,那么c比b优。所以只要有这样的斜率关系,b肯定可以被舍弃。那这样的我们维护的一个图形画出来就是一个下凸包。
然后用单调队列维护他就可以了,注意这是在x单调,y单调的情况下,才可以用单调队列维护。还需要注意的是为了表示可以从什么都不选的情况递推过来,需要在单调队列加入一个0节点。因为这个WA了无数发。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注