BZOJ1597_土地购买_KEY
2024-10-19 17:22:38
一道斜率优化的题目。
但暴力方程很关键。
我们先将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 ;
}
最新文章
- 解决Android studio 非法字符的问题
- 系统配置 之:远程桌面连接(win7系统)
- java 多线程断点下载demo
- MySQL5.5半同步模式
- 关于H5+css3的一些简单知识
- HTTP缓存 1.0 vs 1.1
- open函数
- JspContext对象与PageContext对象
- springboot添加swagger2组件
- django2.0+linux服务器 ,如何让自己电脑访问
- 推荐几个IDEA插件,Java开发者撸码利器。
- Linux系统编程之事件驱动
- 微信小程序 + mock.js 实现后台模拟及调试
- js 画布与图片的相互转化(canvas与img)
- 让zepto支持slideup(),slidedown()
- Scratch儿童项目式编程—捉迷藏游戏 Scratch children project programming - hide-and-seek game
- Ajax与select标签的组合运用
- yum更换阿里源
- Struts框架之结果页面的跳转
- java Concurrent包学习笔记(三):ReentrantLock