题目传送门

一道斜率优化的题目。

但暴力方程很关键。

我们先将x作为关键字Sort一遍,再将y处理成单调递减,即把无用的土地去除。

f[i]=f[j]+a[i]*b[j+]
-a[i]*b[j+]+f[i]=f[j]
k x + b = y

然后单调队列维护凸包做斜率优化就好了。

code:

/**************************************************************
Problem: 1597
User: yekehe
Language: C++
Result: Accepted
Time:104 ms
Memory:3268 kb
****************************************************************/ #include <cstdio>
#include <algorithm>
using namespace std; char tc()
{
static char tr[],*A=tr,*B=tr;
return A==B&&(B=(A=tr)+fread(tr,,,stdin),A==B)?EOF:*A++;
} int read()
{
char c;while(c=tc(),c<''||c>'');
int x=c-'';while(c=tc(),c>=''&&c<='')x=x*+c-'';
return x;
} int N,tot;
struct node{long long x,y;}a[],c[];
inline int cmp(node x,node y){return x.x<y.x;} long long l[],h,t,f[]; double X(int x){return c[x+].y;}
double Y(int y){return f[y];}
double get(int x,int y){return (Y(y)-Y(x))/(X(y)-X(x));} int main()
{
N=read();
register int i;
for(i=;i<=N;i++)a[i].x=read(),a[i].y=read();
sort(a+,a+N+,cmp);
for(i=;i<=N;i++){
while(tot&&a[i].y>=c[tot].y)tot--;
c[++tot]=a[i];
}
h=t=;
for(i=;i<=tot;i++){
while(h<t&&-c[i].x<get(l[h],l[h+]))h++;
int j=l[h];f[i]=f[j]+c[i].x*c[j+].y;
while(h<t&&get(l[t-],l[t])<get(l[t],i))t--;
l[++t]=i;
}
printf("%lld",f[tot]);
return ;
}

最新文章

  1. 解决Android studio 非法字符的问题
  2. 系统配置 之:远程桌面连接(win7系统)
  3. java 多线程断点下载demo
  4. MySQL5.5半同步模式
  5. 关于H5+css3的一些简单知识
  6. HTTP缓存 1.0 vs 1.1
  7. open函数
  8. JspContext对象与PageContext对象
  9. springboot添加swagger2组件
  10. django2.0+linux服务器 ,如何让自己电脑访问
  11. 推荐几个IDEA插件,Java开发者撸码利器。
  12. Linux系统编程之事件驱动
  13. 微信小程序 + mock.js 实现后台模拟及调试
  14. js 画布与图片的相互转化(canvas与img)
  15. 让zepto支持slideup(),slidedown()
  16. Scratch儿童项目式编程—捉迷藏游戏 Scratch children project programming - hide-and-seek game
  17. Ajax与select标签的组合运用
  18. yum更换阿里源
  19. Struts框架之结果页面的跳转
  20. java Concurrent包学习笔记(三):ReentrantLock

热门文章

  1. 学习python第一天总纲
  2. UVa 11346 - Probability(几何概型)
  3. CF284A Cows and Primitive Roots
  4. python沙箱逃逸的几道题
  5. Odoo中的模型
  6. ThinkPHP5入门(二)----控制器篇
  7. nginx开启gzip
  8. Dubbo实践(六)Spring加载Bean流程
  9. openstack 虚拟机 迁移
  10. JavaScript or jQuery 获取option value值 以及文本内容的方法