博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[HDU3507]Print Article
阅读量:5840 次
发布时间:2019-06-18

本文共 1979 字,大约阅读时间需要 6 分钟。

[HDU3507]Print Article

题面

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

1669439-20190530101348277-1496885493.jpg

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 559575

Sample Output

230

思路

这是一道斜率优化dp的经典例题。

很显然,我们可以得出状态转移方程:

\[f[i]=min(f[j]+(s[i]-s[j])^2+M),1\leq j< i\]

化简一波可以得到:

\(f[i]=min(f[j]+s[j]^2-2s[i]s[j])+M+s[i]^2\)

那么,我们令\(k=-2s[j],x=s[i],b=f[j]+s[j]^2,y=kx+b\)

那么对于直线\(x=s[i]\),与任意直线\(y=kx+b,k=-2s[j]\)的交点(s[i],h),h就意味着\(min(f[j]+s[j]^2-2s[i]s[j])\)的值。

显然,对于第\(i\)次转移,我们可以把\([1,i-1]\)次转移时的\(min(f[j]+s[j]^2-2s[i]s[j])\)看成\(i-1\)条线段,然后在\(s[i]\)的位置作一条垂直于\(x\)轴的直线,与之交点最低的那条直线对应的编号就是最优的转移对象。

我们可以维护一个上凸壳,每次加入的直线(对于每个i,转移完成后就会变成直线加入)后先判断\(i和i-1\)以及\(i-1和i-2\)这两条直线交点横坐标的大小关系。如果前者小于后者,很显然\(i-1\)这条线就没用了。

代码

#include
#include
#include
#include
using namespace std;#define maxn (int)(5e5+100)#define ll long longstruct gg{ ll b,k;}l[maxn];int head,tail,c[maxn],n,m;ll s[maxn],f[maxn];bool cmp(gg l1,gg l2,int c){return (double)(l2.b-l1.b)/(l1.k-l2.k)<=c;}bool cmp(gg l1,gg l2,gg c){return (double)(l2.b-l1.b)/(l1.k-l2.k)>=(double)(c.b-l1.b)/(l1.k-c.k);}ll solve(){ head=1,tail=0,l[++tail]=(gg){0,0}; for(int i=1;i<=n;i++){ s[i]=s[i-1]+c[i]; while(head

转载于:https://www.cnblogs.com/GavinZheng/p/10942944.html

你可能感兴趣的文章
Git分支2
查看>>
一键安装Gitlab后的备份、迁移与恢复
查看>>
因为本人工作繁忙,精力有限,本博客停止更新。有兴趣的博友可以关注我在CSDN上的主博客...
查看>>
SQL server查看触发器是否被禁用
查看>>
[C++基础]在构造函数内部调用构造函数
查看>>
跟随我在oracle学习php(8)
查看>>
Spring 3.1.0 Hibernate 3.0 Eclipse Spring WEB例子
查看>>
UVA-10212 The Last Non-zero Digit. 分解质因子+容斥定理
查看>>
求两个集合的交集,并集,差集
查看>>
Kotlin的语法糖(一)基础篇
查看>>
OkHttp源码分析
查看>>
让你的app体验更丝滑的11种方法!冲击手机应用榜单Top3指日可待
查看>>
windows kernel exploitation基础教程
查看>>
NS_OPTIONS枚举的用法
查看>>
java9系列(九)Make G1 the Default Garbage Collector
查看>>
QAQ高精度模板笔记√
查看>>
Jmeter计数器的使用-转载
查看>>
【Android笔记】入门篇02:全屏设置和禁止横屏竖屏切换
查看>>
4. Median of Two Sorted Arrays
查看>>
Kubernetes的本质
查看>>