2018.09.10 bzoj1597: [Usaco2008 Mar]土地购买(斜率优化dp)

时间:2022-06-21 14:59:12

传送门

终究还是通宵了啊。。。

这是一道简单的斜率优化dp。

先对所有土地排序,显然如果有严格小于的两块土地不用考虑小的一块。

于是剩下的土地有一条边单增,另外一条单减。

我们假设a[i]是单减的,b[i]是单增的。

f[i]=min(f[j]+a[j+1]∗b[i])" role="presentation" style="position: relative;">f[i]=min(f[j]+a[j+1]∗b[i])f[i]=min(f[j]+a[j+1]∗b[i])

对于两个决策k1&lt;k2" role="presentation" style="position: relative;">k1<k2k1<k2,如果k2优于k1,那么:

f[k1]−f[k2]&gt;b[i]∗(a[k2+1]−a[k1+1])" role="presentation" style="position: relative;">f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])

注意a是单减的除过去要变号。

<=>slope&lt;b[i]" role="presentation" style="position: relative;">slope<b[i]slope<b[i]

于是可以斜率优化了。

代码:

#include<bits/stdc++.h>
#define N 50005
#define ll long long
using namespace std;
inline ll read(){
    ll ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int n,tot=0,hd,tl,q[N];
ll f[N];
struct Node{ll a,b;}p_[N],p[N];
inline bool cmp(Node a,Node b){return a.a==b.a?a.b>b.b:a.a>b.a;}
inline double slope(int i,int j){return (f[i]-f[j])*1.0/(p[j+1].a-p[i+1].a);}
int main(){
    n=read(),hd=tl=1;
    for(int i=1;i<=n;++i)p_[i].a=read(),p_[i].b=read();
    sort(p_+1,p_+n+1,cmp);
    for(int i=1;i<=n;++i)if(tot==0||p_[i].b>p[tot].b)p[++tot]=p_[i];
    for(int i=1;i<=tot;++i){
        while(hd<tl&&slope(q[hd],q[hd+1])<p[i].b)++hd;
        int j=q[hd];
        f[i]=f[j]+p[i].b*p[j+1].a;
        while(hd<tl&&slope(q[tl],i)<slope(q[tl-1],q[tl]))--tl;
        q[++tl]=i;
    }
    cout<<f[tot];
    return 0;
}

2018.09.10 bzoj1597: [Usaco2008 Mar]土地购买(斜率优化dp)的更多相关文章

  1. bzoj1597&lbrack;Usaco2008 Mar&rsqb;土地购买 斜率优化dp

    1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 5524  Solved: 2074[Submit] ...

  2. bzoj1597 &lbrack;Usaco2008 Mar&rsqb;土地购买——斜率优化DP

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1597 就是斜率优化水题... 然而WA了十几遍,正负号处理真让人心累... 还是该负就负,别 ...

  3. BZOJ 1597&colon; &lbrack;Usaco2008 Mar&rsqb;土地购买 &lbrack;斜率优化DP&rsqb;

    1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4026  Solved: 1473[Submit] ...

  4. &lbrack;Bzoj1597&rsqb;&lbrack;Usaco2008 Mar&rsqb;土地购买&lpar;斜率优化&rpar;

    题目链接 因为题目说可以分组,并且是求最值,所以斜率优化应该是可以搞的,现在要想怎么排序使得相邻的数在一个组中最优. 我们按照宽$w$从小到大,高$h$从小到大排序.这时发现可以筛掉一些一定没有贡献的 ...

  5. BZOJ1597&colon; &lbrack;Usaco2008 Mar&rsqb;土地购买——斜率优化

    题目大意: 将$n$个长方形分成若*分,每一部分的花费为部分中长方形的$max_长*max_宽$(不是$max_{长*宽}$),求最小花费 思路: 首先,可以被其他长方形包含的长方形可以删去 然后我 ...

  6. bzoj 1597 &lbrack;Usaco2008 Mar&rsqb;土地购买——斜率优化dp

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1597 又一道斜率优化dp.负数让我混乱.不过仔细想想还是好的. 还可以方便地把那个负号放到x ...

  7. BZOJ 1597&colon; &lbrack;Usaco2008 Mar&rsqb;土地购买 斜率优化

    1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MB Description 农夫John准备扩大他的农场,他正在考虑N ...

  8. 【斜率DP】bzoj1597&colon; &lbrack;Usaco2008 Mar&rsqb;土地购买

    1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2474  Solved: 900[Submit][ ...

  9. Bzoj1597 &lbrack;Usaco2008 Mar&rsqb;土地购买

    Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4005  Solved: 1460 Description 农夫John准备扩大他的农场,他正在考虑N ...

随机推荐

  1. JS判断登陆端是PC还是手机

    前些天朋友问我怎么判断登陆端是PC还是手机...自己也是很困惑,然后自己查了资料,这些东西都藏在USER-AGENT里面,查了他的一些属性,写了一个简单的验证页面大家共同学习. 读取navigator ...

  2. 常用命令(ubuntu)

    1.打开终端的方法 Ubuntu 中按左侧栏的第一个“面板主页(Dash 主页)”(可以按win键调出),在里面输入terminal可以打开终端,另外打开终端的快捷键是Ctrl+Alt+T 2.修改用 ...

  3. ubuntu安装水星MW150US无线网卡8188eu驱动

    买了一个无线网卡插在ubuntu系统的电脑上,却不能识别出来.lsusb,可以看到下面的结果: Bus 002 Device 002: ID 0bda:8179 Realtek Semiconduct ...

  4. Lodop、c-lodop注册与角色简短问答

    注册与角色:参考http://www.c-lodop.com/demolist/t1.html参考链接里的三种场景,是哪种角色.客户端访问网站后用自己的打印机打印.是客户端本地打印角色.IP和域名注册 ...

  5. 13&colon; vue项目结构搭建与开发

    vue其他篇 01: vue.js安装 02: vue.js常用指令 03: vuejs 事件.模板.过滤器 目录: 1.1 初始化项目 1.2 配置API接口,模拟后台数据 1.3 项目整体结构化开 ...

  6. 【Spring】SpringMVC之REST编程风格

    REST架构是一个抽象的概念,目前主要是基于HTTP协议实现,其目的是为了提高系统的可伸缩性.降低应用之间的耦合度.便于架构分布式处理程序.当使用多种语言进行开发的时候,每一种语言对URL的处理不同, ...

  7. 一个脚本和一个容易疏忽的问题strcmp、strncmp、memcmp的用法【原创】

    一个容易疏忽的问题: strcmp.strncmp.memcmp, 对于memcmp进行字符串比较时可能会出现内存重叠的情况 status = strncmp(xdev->product, &q ...

  8. &sol;etc&sol;hostname

    我们可以使用 hostname 命令来修改主机名,但只是临时生效,如果想永久生效可以编辑 /etc/hostname 文件,注意不是每个 Linux 发行版都有该文件 root@Ubuntu_Lee: ...

  9. Codeforces Round &num;513 by Barcelona Bootcamp

    A. Phone Numbers 签. #include <bits/stdc++.h> using namespace std; #define N 110 char s[N]; ], ...

  10. 用纯css改变默认的radio和checkbox的样式

    利用css的label的伪类(::before)代替checkbox和radio效果: 优点:需要图片来调整选中前和选中后的样式,纯css搞定 缺点:兼容性,IE8以下不支持 在线例子: css改变默 ...