[USACO2008 Mar]土地购买
2024-10-18 20:54:08
传送门:>HERE<
题意:购买一组土地的费用是最长的长乘以最长的宽。现给出n块土地,求购买所有土地(可以将土地分为任意组,不需按顺序)的最小费用
解题思路
动态规划+斜率优化
斜率优化在这道题里并不难,关键是第一步的方程以及思想
由于买一组土地的关键是最大的长和宽,所以设任意两块土地$x, y$,若$w[x] \leq w[y] 且 l[x] \leq l[y]$,那么我们可以把$x, y$放在一组里,这样x存不存在都一样。因此x就可以扔掉不管了。所以第一步我们可以把所有没用的都扔掉。
那么怎么扔呢?首先对所有土地以高度为第一关键字,宽度为第二关键字从小到大排序。直接利用单调栈踢出所有没用的土地——然后让每一块土地依次进栈,由于高度是单调递增的,那么如果当前土地的宽度 $\geq$ 栈顶的宽度,也就意味着栈顶那块就没用了,因此可以pop
这样做有什么好处?令$f[i]$表示购买前i块土地的费用,枚举断点j,得状态转移方程$$f[i] = f[j] + h[i] * w[j+1]$$由于现在栈内已经单调,根据递增与递减的性质,就可以O(1)求得这一区间土地长宽的最大最小值了
然后就可以做斜率优化的DP了。
Code
long long
坑点挺多的,调了一上午。先是x坐标移项之后是负的,并且栈溢出要判断,不然top减成负数了。
/*By QiXingzhi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
#define int long long
const int MAXN = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
struct Land{ int w,h; }a[MAXN],A[MAXN];
int n,top,h,t,sta[MAXN],q[MAXN],f[MAXN];
inline bool comp(const Land& a, const Land& b){ return (a.h != b.h) ? a.h < b.h : a.w < b.w; }
inline double X(int i){ return -A[i+].w; }
inline double Y(int i){ return f[i]; }
inline double Slope(int i, int j){ return (double)(Y(i)-Y(j)) / (double)(X(i)-X(j)); }
main(){
n = r;
for(int i = ; i <= n; ++i) a[i].w = r, a[i].h = r;
sort(a+, a+n+, comp);
sta[++top] = ;
for(int i = ; i <= n; ++i){
while(top> && a[i].w >= a[sta[top]].w) --top;
sta[++top] = i;
}
for(int i = ; i <= top; ++i) A[i] = a[sta[i]];
for(int i = ; i <= top; ++i){
while(h<t && Slope(q[h],q[h+]) < A[i].h) ++h;
f[i] = f[q[h]] + A[q[h]+].w * A[i].h;
while(h<t && Slope(q[t],q[t-]) > Slope(q[t],i)) --t;
q[++t] = i;
}
printf("%lld", f[top]);
return ;
}
最新文章
- Java中分割字符串
- avalon全选效果分析讲解
- LeetCode #303. Range Sum Query
- 如何使用参数 appActivity+appPackage 和 app
- 使用cocos2d-x v3.1开发小游戏(基本框架)
- 想学习一下CSS函数
- linux命令:rm
- (六)6.8 Neurons Networks implements of PCA ZCA and whitening
- ie6的兼容总结
- sql server使用说明
- HDU2093--考试排名
- MySQL临时表与派生表(简略版)
- Hibernate配置文件中配置各种数据库链接
- iOS 图片本地存储、本地获取、本地删除
- 个人项目--“”小鱼企业级开发系统“”Svn地址分享
- (八)java垃圾回收和收尾
- Linux 显示权限
- Jvm 中的 重排序、主存、原子操作
- LR12集合点设置和多个负载生成器策略
- (整理4)RPC服务和HTTP服务简单说明