【题解】[USACO08MAR]Land Acquisition G
2024-09-03 20:37:43
题目大意:给定\(n\)个二元组,每次可以选择一组,花费是组内最大的长乘以最大的宽。问消掉所有二元组的最小代价。
\(\text{Solution:}\)
\(dp\)写的不够啊……
先挖掘一下题目性质,对于一个二元组,如果它的长和宽都可以被某一个二元组覆盖掉,则它显然是可以被并掉的,于是我们去掉。
这个是一遍\(sort\)就能解决的。
那么,我们把数组搞成一个长递减,宽递增的数列,设\(dp[i]\)表示前\(i\)个二元组全部消掉的最小价值。
可以证明,在这个情况下,我们买的土地都是连续的。因为如果不连续,则总有一块更大的可以把之前不连续的一段包进去,这显然是不优的。
于是,\(dp\)经典模型,\(dp[i]=\min_{j<i}dp[j]+x[j+1]*y[i].\)之所以这样写,是因为\(y\)是递增的,它可以覆盖到它前面所有;\(x\)递减,可以覆盖到后面的所有。
下面是最简单的推柿子。
\[dp[i]=dp[j]+x[j+1]*y[i]
\]
\]
\[dp[j]=dp[i]-x[j+1]*y[i]
\]
\]
\[dp[j]=-x[j+1]*y[i]+dp[i]
\]
\]
\[y=dp[j],k=y[i],x=-x[j+1],b=dp[i]
\]
\]
至此,\(y=kx+b\)初成。
于是,我们最小化截距就做完了。观察一下符号,显然地发现是下凸包。又有斜率\(y[i]\)是递增的,所以套路维护大于当前斜率的即可。
剩下的都是板子。这题主要学到了:认真观察题目性质,这种的可以一遍\(\text{sort}\)去掉,剩下的可以简单证明是连续的,从而化成一个\(dp\)的基本模型。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,tot,head,tail;
int q[200010],dp[200010];
struct node{
int x,y;
bool operator<(const node&B)const{
return x==B.x?y>B.y:x>B.x;
}
}a[200010];
int X(int x){return -a[x+1].x;}
int Y(int x){return dp[x];}
long double slope(int x,int y){return (Y(y)-Y(x))/(X(y)-X(x));}
//dp[i]=dp[j]+y[j+1]*x[i]
//dp[j]=-y[j+1]*x[i]+dp[i]
//y=dp[j],k=x[i],x=-y[j+1],b=dp[i]
//dp[j]+a[j+1].y*x[i]>dp[k]+a[k+1].y*x[i]
// a[j+1].y*x[i]-a[k+1].y*x[i]>dp[k]-dp[j]
//x[i](a[j+1].y-a[k+1].y)>dp[k]-dp[j]
//x[i]>(dp[k]-dp[j])/(a[j+1].y-a[k+1].y)
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].x,&a[i].y);
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){if(a[i].y>a[tot].y)a[++tot]=a[i];}//x递减,y递增
//令y是斜率,则可以维护一个下凸包
//dp[i]=dp[j]+a[j+1].x*a[i].y
//注意此处x递减,y递增,斜率递增,可以On
//既然x递减,那么x限定的范围就是x到后面的i.x
//所以应该枚举的j.x来限定x而不是y
//因为y递增,所以它限定前面
//这题的收获有两个:
//一个是挖掘题目性质,去掉无用点
//而是注意到单调性,进而斜率优化
head=tail=1;q[head]=0;n=tot;
for(int i=1;i<=tot;++i){
while(head<tail&&slope(q[head],q[head+1])<=a[i].y)head++;
dp[i]=dp[q[head]]+a[q[head]+1].x*a[i].y;
while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail-1],i))tail--;
q[++tail]=i;
}
printf("%lld\n",dp[n]);
return 0;
}
代码里面也有一些细节。
最新文章
- Webwork 学习之路【08】结合实战简析Controller 配置
- 线程的Alertable与User APC
- C# unity3d 贪吃蛇 游戏 源码 及其感想
- RSA加密解密(python版)
- SHGetFileInfo函数详解
- a与a:link、a:visited、a:hover、a:active
- H5案例学习笔记
- Java程序内存分析:使用mat工具分析内存占用
- poj 2411 Mondriaan&#39;s Dream_状态压缩dp
- hdu4171 Paper Route 树的性质+DFS
- C++获取Windows7 32位系统中所有进程名(类似于任务管理器中的进程)
- Numpy入门 - 数组排序
- asp.net core 系列之中间件基础篇(middleware)
- zeppelin中连接hive和impala
- django(models)视图与html 简单的操作
- dotnet core使用IO合并技巧轻松实现千万级消息推送
- CRM 2016 Get IOrganizationService
- do_bootrk
- Win7/8/10十个最强大通用快捷键
- Liunx-history命令