BZOJ 1597: [Usaco2008 Mar]土地购买动态规划 + 斜率优化

秒速五厘米 2021-11-16 05:26 214阅读 0赞

Code:

#include<bits/stdc++.h> 
    #define maxn 1000000 
    #define ll long long 
    #define x(i) (b[i+1]) 
    #define y(i) (f[i]) 
    #define setIO(s) freopen(s".in","r",stdin) 
    using namespace std;  
    int A[maxn],arr[maxn],q[maxn],tot,head,tail;  
    ll a[maxn], b[maxn], f[maxn], u[maxn], v[maxn];         
    bool cmp(int i,int j) 
    {
        return u[i]==u[j]?v[i]<v[j]:u[i]<u[j]; 
    }
    double slope(int i,int j)
    {
        return (double)(1.00*y(i)-y(j))/(double)(1.00*x(j)-x(i));       
    }
    int main()
    {
        // setIO("input"); 
        int n,i,j; 
        scanf("%d",&n);   
        for(i=1;i<=n;++i) scanf("%lld%lld",&u[i],&v[i]),A[i]=i; 
        sort(A+1,A+1+n,cmp);   
        for(i=1;i<=n;++i) 
        { 
            while(v[A[i]]>=b[tot]&&tot) --tot; 
            ++tot, a[tot]=u[A[i]], b[tot]=v[A[i]];  
        }
        n=tot,head=tail=0;  
        for(i=1;i<=n;++i) 
        {           
            while(head<tail&&slope(q[head],q[head+1])<a[i]) ++head; 
            f[i]=f[q[head]]+a[i]*b[q[head]+1];               
            while(head<tail&&slope(q[tail], i)<slope(q[tail-1],i)) --tail; 
            q[++tail]=i; 
        }
        printf("%lld\n",f[n]);     
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11139251.html

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划进阶 — — 斜率优化【3】

动态规划进阶 — — 斜率优化【3】 1 打怪兽问题 ![在这里插入图片描述][64870f8dd11b4fffb0c0830f011521f4.png] 1.

朱雀/ 2024年04月06日 09:27/ 0 赞/ 37 阅读

相关【计算几何】【斜率】bzoj1610 [Usaco2008 Feb]Line连线游戏

枚举直线，计算斜率，排序，统计答案。 include<cstdio> include<cmath> include<algorithm> us

ゞ浴缸里的玫瑰/ 2022年01月07日 01:15/ 0 赞/ 103 阅读

相关【BZOJ】1607: [Usaco2008 Dec]Patting Heads 轻拍牛头

【算法】模拟 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] include<cstdio> in

今天药忘吃喽~/ 2022年01月05日 06:15/ 0 赞/ 108 阅读

相关 bzoj1604[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居*

[bzoj1604\[Usaco2008 Open\]Cow Neighborhoods 奶牛的邻居][bzoj1604_Usaco2008 Open_Cow Neighbor

逃离我推掉我的手/ 2021年12月24日 19:39/ 0 赞/ 205 阅读

相关 [Usaco2008 Mar]River Crossing渡河问题

题目描述 Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程

你的名字/ 2021年12月24日 16:21/ 0 赞/ 209 阅读

相关 BZOJ 1010: 玩具装箱toy (斜率优化dp)

Description 　　P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种

拼搏现实的明天。/ 2021年12月03日 06:19/ 0 赞/ 216 阅读

相关 BZOJ 1740: [Usaco2005 mar]Yogurt factory 奶酪工厂贪心 + 问题转化

Description The cows have purchased a yogurt factory that makes world-famous Yucky Yo

ゝ一纸荒年。/ 2021年11月17日 16:22/ 0 赞/ 424 阅读

相关 luoguP2365 任务安排斜率优化 + 动态规划

Code: include<bits/stdc++.h> define setIO(s) freopen(s".in","r",stdin) de

约定不等于承诺〃/ 2021年11月17日 16:22/ 0 赞/ 294 阅读

相关 BZOJ 1597: [Usaco2008 Mar]土地购买动态规划 + 斜率优化

Code: include<bits/stdc++.h> define maxn 1000000 define ll long long

秒速五厘米/ 2021年11月16日 05:26/ 0 赞/ 215 阅读

相关 [USACO10MAR]伟大的奶牛聚集

题目描述 Bessie is planning the annual Great Cow Gathering for cows all across the countr

谁践踏了优雅/ 2021年11月04日 22:04/ 0 赞/ 598 阅读