[LuoguP2900] [USACO08MAR]土地征用(Land Acquisition)
土地征用 (Link)
约翰准备扩大他的农场,眼前他正在考虑购买N块长方形的土地。如果约翰单买一块土 地,价格就是土地的面积。但他可以选择并购一组土地,并购的价格为这些土地中最大的长 乘以最大的宽。比如约翰并购一块3 × 5和一块5 × 3的土地,他只需要支付5 × 5 = 25元, 比单买合算。 约翰希望买下所有的土地。他发现,将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸,请你帮助他计算购买所有土地所需的最小费用。
输入输出格式
输入格式:
\(Line\) \(1:\) \(A\) \(single\) \(integer:\) \(N\)
\(Lines\) \(2..N+1:\) \(Line\) \(i+1\) \(describes\) \(plot\) \(i\) \(with\) \(two\) \(space-separated\) \(integers:\) \(width\) _ \(i\) \(and\) \(length\) _ \(i\)
输出格式:
\(Line\) \(1:\) \(The\) \(minimum\) \(amount\) \(necessary\) \(to\) \(buy\) \(all\) \(the\) \(plots.\)
我们定义结构体\(Edge\)中含有\(X,Y\)分别表示一块土地的长和宽。
考虑一块土地\(A\),如果有一块土地\(B\)的\(X\)和\(Y\)都大于\(A\),那么\(A\)的存在是没有意义的,因为\(A\)是可以不耗费任何代价被\(B\)所合并的,所以它不会对答案产生任何影响。于是我们考虑去掉这样所有的土地\(A\)。
首先我们将所有土地按照长度从小到大排序,长度相同的按照宽度从小到大排序。定义一个\(Stack\),然后连续将所有的土地入栈,在\(A\)入栈之前将之前栈中所有宽度小于等于\(A\)的土地全部弹出,然后入栈\(A\)。那么最后在栈中的元素就是我们所希望的元素。这里的元素是按照长度从小到大,宽度从大到小的顺序有序排列的。
那么显然我们每次合并的都是一个连续的区间。考虑使用\(DP\),易得状态转移方程:\(dp[i]=min_{j=1}^{j<=Top}(dp[i],dp[j]+Stack[j+1]*L[i])\),其中Stack里面存的是元素的宽度,L是栈中元素的长度。(因为有些土地被抛弃了所以我们不能继续使用\(Edge\)结构体),然而这样的时间复杂度会超时,考虑斜率优化。
我们看到后面的\(dp[j]+Stack[j+1]*L[i]\),设\(k=Stack[j+1],b=dp[j]\),然后\(x=L[i]\),那么我们就得到了直线方程:\(y=kx+b\)。套上斜率优化的板子即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define LL long long
#define INF 0x7fffffff
using namespace std ;
LL N, Stack[MAXN], Top;
LL dp[MAXN], q[MAXN];
LL A[MAXN], B[MAXN];
LL L[MAXN];
inline void Read(LL & x){
char C = getchar() ; x = 0 ;
while(C < '0' || C > '9') C = getchar() ;
while(C <= '9' && C >= '0')
x = x * 10 + C - 48, C = getchar() ;
}
inline void Print(LL x){
LL num = 0 ; char C[15] ;
while(x) C[++ num] = (x % 10) + 48, x /= 10 ;
while(num) putchar(C[num --]) ;
putchar('\n') ;
}
struct Node{
LL X, Y ;
}Edge[MAXN << 1];
inline bool Cmp(Node A, Node B){
if(A.X == B.X) return A.Y < B.Y;
else return A.X < B.X;
}
inline void Put_In_Stack(){
for(int i = 1; i <= N; i ++){
while(Top && Stack[Top] <= Edge[i].Y)
Top -- ;
Stack[++ Top] = Edge[i].Y ;
L[Top] = Edge[i].X ;
}
}
inline double Calc(LL i, LL j){
return dp[j] + Stack[j + 1] * L[i] ;
}
inline bool Slope(LL a, LL b, LL c){
return (B[c] - B[a]) * (A[b] - A[a]) - (B[b] - B[a]) * (A[c] - A[a]) >= 0;
}
int main(){
Read(N) ;
for(int i = 1; i <= N; i ++){
Read(Edge[i].X) ;
Read(Edge[i].Y) ;
}
sort(Edge + 1, Edge + N + 1, Cmp) ;
Put_In_Stack() ;
A[0] = Stack[1] ;
LL Head = 1, Tail = 1 ;
for(int i = 1;i <= Top; i ++){
while(Head < Tail && Calc(i, q[Head]) >= Calc(i, q[Head + 1]))
Head ++ ;
dp[i] = Calc(i, q[Head]) ;
A[i] = Stack[i + 1] ;
B[i] = dp[i] ;
while(Head < Tail && Slope(q[Tail - 1], q[Tail], i))
Tail -- ;
q[++ Tail] = i ;
}
Print(dp[Top]) ; return 0 ;
}
最新文章
- JavaScript面向对象与原型
- WPF中通过代码设置控件的坐标
- mapreduce核心原理
- 解决MVC中使用BundleConfig.RegisterBundles引用Css及js文件发布后丢失的问题
- 论文第4章:iOS绘图平台的实现
- 瞬间从IT屌丝变大神——CSS规范
- 怎样让你的代码更好的被JVM JIT Inlining
- SqlServer Alter Table 语句的用法
- CSS2书写顺序
- jquery 下拉多选插件
- html + CSS
- php学习资料
- windows远程桌面神器
- ECMAScript 6 新特性-set。const
- Android学习笔记(2):build.grandle的常用设置
- 面试题---实现strcpy函数
- [CC-STREETTA]The Street
- Linux kernel 之 uart 驱动解析
- bzoj4945
- Extjs tree1