【BZOJ-1597】土地购买 DP + 斜率优化

1597: [Usaco2008 Mar]土地购买

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit:
2931  Solved: 1091
[Submit][Status][Discuss]

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <=
50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <=
1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换.
如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费.
他需要你帮助他找到最小的经费.

Input

* 第1行: 一个数: N

* 第2..N+1行:
第i+1行包含两个数,分别为第i块土地的长和宽

Output

* 第一行: 最小的可行费用.

Sample Input

4
100 1
15 15
20 5
1
100

输入解释:

共有4块土地.

Sample Output

500

HINT

FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和
15x15 plot. 每组的价格分别为100,100,300, 总共500.

Source

Gold

Solution

DP没什么好说的,至于数据范围,铁定得优化到$O(n/nlogn)$,那么考虑斜率优化

题目大意就是划分多组,每组最长*每组最宽为每组的价值,要求价值最小

很容易发现,如果一块土地,他的长和宽都小于等于他所在组的最长长和最长宽,那么这块土地是没有存在的必要的

那么可以考虑对原始数据进行排序,并用 单调栈 去维护一下长宽,达到目的

这样容易得出转移 $dp[i]=min(dp[j]+y[j+1]*x[i])$

那么进行斜率优化得到$(dp[j-1]-dp[k-1])/(y[j]-y[k])>-x[i]$

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘)ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x;
}
#define maxn 50010
int n,top,que[maxn],l,r;
long long stackx[maxn],stacky[maxn],dp[maxn];
struct Fieldnode
{
    int a,b;
    bool operator < (const Fieldnode & A) const
        {
            if (a==A.a) return b<A.b;
            return a<A.a;
        }
}fie[maxn];
double slope(int i,int j)
{return (dp[j]-dp[i])/(stacky[i+1]-stacky[j+1]);}
int main()
{
    n=read();
    for (int i=1; i<=n; i++)fie[i].a=read(),fie[i].b=read();
    sort(fie+1,fie+n+1);
    for (int i=1; i<=n; i++)
        {
            while (top && fie[i].b>=stacky[top]) top--;
            top++; stackx[top]=fie[i].a; stacky[top]=fie[i].b;
        }
    for (int tmp,i=1; i<=top; i++)
        {
            while (l<r && slope(que[l],que[l+1])<stackx[i]) l++;
            tmp=que[l];
            dp[i]=dp[tmp]+stackx[i]*stacky[tmp+1];
            while (l<r && slope(que[r],i)<slope(que[r-1],que[r])) r--;
            que[++r]=i;
        }
    printf("%lld\n",dp[top]);
    return 0;
} 

一道奶牛题做成这样也是醉了...

时间: 04-10

【BZOJ-1597】土地购买 DP + 斜率优化的相关文章

BZOJ 1597: [Usaco2008 Mar]土地购买【斜率优化+凸包维护】

1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4989  Solved: 1847[Submit][Status][Discuss] Description 农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地

BZOJ 1096: [ZJOI2007]仓库建设(DP+斜率优化)

[ZJOI2007]仓库建设 Description L公司有N个工厂,由高到底分布在一座山上.如图所示,工厂1在山顶,工厂N在山脚.由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用.突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏.由于地形的不同,在不同工厂建立仓库的费用可能是不同的.第i个工厂目前已有成品Pi件,在第i个工厂位置建立仓库的费用是Ci.对于没有建立仓库的工厂,其

【BZOJ-4518】征途 DP + 斜率优化

4518: [Sdoi2016]征途 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 230  Solved: 156[Submit][Status][Discuss] Description Pine开始了从S地到T地的征途. 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站. Pine计划用m天到达T地.除第m天外,每一天晚上Pine都必须在休息站过夜.所以,一段路必须在同一天中走完. Pine希望每一天走的路长度尽可能相近,所以他

学渣乱搞系列之dp斜率优化

学渣乱搞系列之dp斜率优化 By 狂徒归来 貌似dp的斜率优化一直很难搞啊,尤其是像我这种数学很挫的学渣,压根不懂什么凸包,什么上凸下凸的,哎...说多了都是泪,跟wdd讨论了下,得出一些结论.本文很大部分参考了大神Accept的文章,不过此神貌似早已绝迹江湖,这篇文章写得好,也写得很差,前半部分叙述得很好,可是关键,关键部分说得很乱,有些许错误,很多大神都进行了评论指出,但是大神Accept貌似没有修改的意思,故重新总结下,以便自己以后查阅和复习啊. 下面看一个例题Print Article.

Covered Walkway(HDU4258,dp斜率优化)

Covered Walkway Time Limit: 30000/10000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Problem Description Your university wants to build a new walkway, and they want at least part of it to be covered. There are certain points which

BZOJ 1010: [HNOI2008]玩具装箱toy [DP 斜率优化]

1010: [HNOI2008]玩具装箱toy Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 9812  Solved: 3978[Submit][Status][Discuss] Description P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京.他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中.P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P

BZOJ 1010: [HNOI2008]玩具装箱toy(DP+斜率优化)

[HNOI2008]玩具装箱toy Description P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京.他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中.P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的.同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为

BZOJ 1096: [ZJOI2007]仓库建设( dp + 斜率优化 )

dp(v) = min(dp(p)+cost(p,v))+C(v) 设sum(v) = ∑pi(1≤i≤v), cnt(v) = ∑pi*xi(1≤i≤v), 则cost(p,v) = x(v)*(sum(v)-sum(p)) - (cnt(v)-cnt(p)) 假设dp(v)由dp(i)转移比dp(j)转移优(i>j), 那么  dp(i)+cost(i,v) < dp(j)+cost(j,v) 即 dp(i)+x(v)*(sum(v)-sum(i))-(cnt(v)-cnt(i)) <

BZOJ 1096 [ZJOI2007]仓库建设 斜率优化dp

1096: [ZJOI2007]仓库建设 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.php?id=1096 Description L公司有N个工厂,由高到底分布在一座山上.如图所示,工厂1在山顶,工厂N在山脚. 由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用.突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场