[USACO08MAR] Land Acquisition G题解

P2900 [USACO08MAR] Land Acquisition G

题目描述

Farmer John 准备扩大他的农场，眼前他正在考虑购买NNN块长方形的土地。

如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块3×53 \times 53×5和一块5×35 \times 35×3的土地，他只需要支付5×5=255 \times 5=255×5=25元， 比单买合算。

FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。

输入格式

第一行一个整数NNN（1≤N≤5×1041 \leq N \leq 5 \times 10^41≤N≤5×104）。

接下来NNN行，每行两个整数wiw_iwi​和lil_ili​，代表第iii块土地的长和宽。保证土地的长和宽不超过10610^6106。

输出格式

输出买下所有土地的最小费用。

输入输出样例 #1

输入 #1

4 100 1 15 15 20 5 1 100

输出 #1

500

说明/提示

将所有土地分为三组：

• 第一块土地为第一组，花费100×1=100100 \times 1=100100×1=100；
• 第二，三块土地为第二组，花费20×15=30020 \times 15=30020×15=300；
• 第四块土地为第三组，花费1×100=1001 \times 100=1001×100=100；

总花费为500500500，可以证明不存在更优的方案。

思路

动态规划 DP
斜率优化

代码见下

#include<bits/stdc++.h>usingnamespacestd;longlongn,m=0,ma=0,f[50004];structone{longlongx,y;}a[50004],b[50004];boolcmp(one a1,one b1){if(a1.x!=b1.x){returna1.x>b1.x;}else{returna1.y>b1.y;}}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i].x>>a[i].y;}sort(a+1,a+n+1,cmp);for(inti=1;i<=n;i++){if(ma<=a[i].y-1){b[++m]=a[i];ma=a[i].y;}}memset(f,62,sizeof(f));f[0]=0;for(inti=1;i<=m;i++){for(intj=max(0,i-1-30000);j<=i-1;j++){if(f[j]+b[j+1].x*b[i].y<f[i]){f[i]=f[j]+b[j+1].x*b[i].y;}//f[i]=min(f[i],f[j]+b[j+1].x*b[i].y);}}cout<<f[m]<<endl;return0;}