hdu3507 Print Article(斜率DP优化)
2024-10-10 05:19:27
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.
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.
InputThere 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.OutputA single number, meaning the mininum cost to print the article.Sample Input
5 5
5
9
5
7
5
Sample Output
230
这是一道斜率优化的模板题吧。斜率优化算是真的弄懂了个大概,不然第一次听的时候什么也不会。
就是开头就是判断一个条件,不断取出头,保证最优,队列中的就是满足1比2优,2比3优,这样,因为后者进入的时间迟,所以又可以成为最优解,我注释了很多。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring> typedef long long LL;
using namespace std; const int NN=; int n,m;
int dp[NN],sum[NN],q[NN]; int GetY(int i,int j)
{
return sum[i]*sum[i]+dp[i]-(sum[j]*sum[j]+dp[j]);
} int GetX(int i,int j)
{
return *(sum[i]-sum[j]);
} int main()
{
int x;
while(~scanf("%d%d",&n,&m))
{
int head=,tail=;
q[tail++]=;//这一步必须,因为可能前i个数全部作为一段才是最小值
for(int i=;i<=n;i++)
{
scanf("%d",&x);
sum[i]=sum[i-]+x;
while(head+<tail&&GetY(q[head+],q[head])<=GetX(q[head+],q[head])*sum[i])
head++;//更新最优的点
dp[i]=(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m+dp[q[head]];//计算dp[i]的最小值
while(head+<tail&&GetY(i,q[tail-])*GetX(q[tail-],q[tail-])<=GetY(q[tail-],q[tail-])*GetX(i,q[tail-]))
tail--;//以k,j,i为判断斜率,然后去掉j。
q[tail++]=i;
}
printf("%d\n",dp[n]);
}
}
最新文章
- webservice wsdl axis2报错 Provider com.bea.xml.stream.MXParserFactory not found
- 2016暑假多校联合---Joint Stacks (STL)
- NSDate 时间比较...等
- 线程本地变量ThreadLocal (耗时工具)
- [php] How to debug PHP in the terminal
- 动态规划(区间DP):HDU 5115 Dire Wolf
- SourceTree 基本介绍
- 《深入理解JAVA虚拟机》笔记1
- LSTM实现中文文本情感分析
- MVC教程四:Controller向View传值的几种方式
- python tuple排序
- java日志 -logback的使用和logback.xml详解(转)
- 如何利用Xshell在Linux下安装jdk
- 75. Sort Colors (Array)
- 系统间接口联调总是报500 for URL 和 乱码
- 苹果Dock样式的菜单
- 背景图片移动插件MyFloatingBg(浮动背景图效果,可让背景随着页面的滚动而滚动)
- vCenter初始化数据中心和集群
- 性能测试工具Jmeter07-Jmeter性能测试实战
- Linux1_Ubuntu的安装