BZOJ 4951 [WF2017]Money for Nothing (决策单调优化DP+分治)
题目大意:略 题目传送门
不愧是$World final$的神题,代码短,思维强度大,细节多到吐..调了足足2h
贪心
我们利用贪心的思想,发现有一些工厂/公司是非常黑心的
以工厂为例,对于一个工厂$i$,如果存在一个工厂$j$,$d_{j}<d_{i},p_{j}<p_{i}$,即出货比i早,而且比i便宜
那么不论我们选择任何消费公司,都一定会选$j$而不是选$i$
消费公司也用类似的贪心方法,消去那些黑心公司
以$d$为$x$轴,$p$为$y$轴,我们得到了许多在二维平面上的点,保证$d_{i}$递增,$p_{i}$递减
这一步贪心可以用单调栈实现
决策单调性
发现我们筛出来这些点以后,并没有什么卵用
假如把这个问题看成一个几何问题,题目转化为,能作为右上角的点视为白点,能作为左下角的点视为黑点,给定很多黑点白点,求白点作为右上角,黑点作为左下角,围成的矩形的面积最大值,且点集内的保证$d_{j}<d_{i},p_{j}<p_{i}$
以下讨论中,点的编号随横坐标$d$增大而增大
大胆地猜测一下,假设我们选择一个左下角黑点$i$,它对应的最优右上角白点是$j$,那么当$j-1$不能和$i$构成最优解时,点$i+1$能否和$j-1$构成最优解呢?
答案是不能,下面给出证明
我们已知$(x_{j}-x_{i})(y_{j}-y_{i})>(x_{j-1}-x_{i})(y_{j-1}-y_{i}),x_{i}<x_{i+1},y_{i}>y_{i+1},x_{j}<x_{j+1},y_{j}>y_{j+1}$
假如能构成最优解,那么$(x_{j-1}-x_{i+1})(y_{j-1}-y_{i+1})>(x_{j}-x_{i+1})(y_{j}-y_{i+1})$
把两式展开,消项可得
$x_{j}\cdot y_{j}-x_{i}\cdot y_{j}-x_{j}\cdot y_{i}>x_{j-1}\cdot y_{j-1}-x_{i}\cdot y_{j-1}-x_{j-1}\cdot y_{i}$
$x_{j-1}\cdot y_{j-1}-x_{i+1}\cdot y_{j-1}-x_{j-1}\cdot y_{i+1}>x_{j}\cdot y_{j}-x_{i+1}\cdot y_{j}-x_{j}\cdot y_{i+1}$
不等号方向相同,两式相加,消去相同项,可得
$-x_{i}\cdot y_{j}-x_{j}\cdot y_{i}-x_{i+1}\cdot y_{j-1}-x_{j-1}\cdot y_{i+1}>-x_{i}\cdot y_{j-1}-x_{j-1}\cdot y_{i}-x_{i+1}\cdot y_{j}-x_{j}\cdot y_{i+1}$
合并,整理可得
$(x_{i+1}-x_{i})(y_{j-1}-y_{j})+(y_{i}-y_{i+1})(x_{j}-x_{j-1})<0$
由于$x_{i}<x_{i+1},y_{i}>y_{i+1},x_{j}<x_{j+1},y_{j}>y_{j+1}$,上述式子一定大于$0$,所以这种情况不存在
分治求解
我们刚刚发现了这个优美的性质,接下来该如何利用这个性质求解呢?
考虑分治,用类似于整体二分的方法,把右上角的点看成询问,左下角的点视为操作(决策)
当前的询问区间是$[l1,r1]$,决策区间是$[l2,r2]$
现在选择了询问区间的重点$mid$,遍历$[l2,r2]$找到$mid$的决策$p$
根据决策单调性,$[l1,mid-1]$的决策一定属于$[l2,p]$,$[mid+1,r1]$的决策一定属于$[p,r2]$
类似于整体二分的方法,递归即可
繁多的细节
你作为中国代表队的一员参加了$ACM$,成功晋级$World Final$,然后你一眼看出了贪心,决策单调性,以及靠谱的分治算法,你抢过队友的键盘开始码这道题
不过这道题代码实现的细节还挺多的
首先,分治算法中,$mid$的决策$p$可能有多个,它们中的某几个可能同时作为$[l1,mid-1]$和$[mid+1,r1]$的决策
所以我们要把所有的决策$p$全都推到两边分治
但如果$mid$找不到决策怎么办?
找到最大的可能作为$[l1,mid-1]$和$[mid+1,r1]$的决策区间,继续递归
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 500010
#define ll long long
#define dd double
#define inf 1333333333
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
} int n,m,nn,mm; int stk[N1],tp; ll ans;
struct node{int x,v;}a[N1],b[N1],tmp[N1];
int cmp1(node s1,node s2){ if(s1.x!=s2.x) return s1.x<s2.x; return s1.v<s2.v; }
int cmp2(node s1,node s2){ if(s1.x!=s2.x) return s1.x<s2.x; return s1.v>s2.v; } int de;
void solve(int l1,int r1,int l2,int r2)
{
if(l1>r1||l2>r2) return;
int mid=(l1+r1)>>,i,S=-,E=-; ll ma=-,tmp;
for(i=l2;i<=r2;i++)
{
tmp=1ll*(b[mid].v-a[i].v)*(b[mid].x-a[i].x);
if(b[mid].x<a[i].x||b[mid].v<a[i].v) tmp=-inf;
if(tmp>ma) ma=tmp,S=E=i;
else if(tmp==ma) E=i;
}
if(S==-&&E==-)
{
de=;
if(l1<=mid+&&mid+<=r1)
for(i=l2;i<=r2;i++) if(b[mid+].v>=a[i].v){
solve(mid+,r1,i,r2); break; }
if(l1<=mid-&&mid-<=r1)
for(i=r2;i>=l2;i--) if(b[mid-].x>=a[i].x){
solve(l1,mid-,l2,i); break; }
return;
}
ans=max(ans,ma);
solve(l1,mid-,l2,E); solve(mid+,r1,S,r2);
} int main()
{
scanf("%d%d",&m,&n);
int i;
for(i=;i<=m;i++){ a[i].v=gint(); a[i].x=gint(); }
for(i=;i<=n;i++){ b[i].v=gint(); b[i].x=gint(); } sort(a+,a+m+,cmp1);
for(tp=,i=m;i;i--)
{
while(tp>=&&a[i].v<=a[stk[tp]].v) tp--;
stk[++tp]=i;
}
for(i=;i<=tp;i++) tmp[i]=a[stk[i]];
for(i=;i<=tp;i++) a[i]=tmp[tp-i+];
mm=tp; sort(b+,b+n+,cmp2);
for(tp=,i=;i<=n;i++)
{
while(tp>=&&b[i].v>=b[stk[tp]].v) tp--;
stk[++tp]=i;
}
for(i=;i<=tp;i++) tmp[i]=b[stk[i]];
for(i=;i<=tp;i++) b[i]=tmp[i];
nn=tp; solve(,nn,,mm);
printf("%lld\n",ans);
return ;
}
最新文章
- 荷兰国旗 Flag of the Kingdom of the Netherlands
- git 本地库推送远程库 版本冲突的解决方法
- cocos2dx 3.x(精灵的碰撞检测,点击移动与拖动精灵)
- Linux ARM kernel Makefile and Kconfig
- 【JavaScript】关于prototype
- knowledge about apache
- 字体圆润属性的使用-webkit-font-smoothing: antialiased
- ECMAScript 6 模块简介
- 用windows live writer写博客
- javascript第一课练习
- CodeIgniter入门——HelloWorld
- 一篇文章让你搞懂 SSL 证书
- html超级简单实现点赞(收藏)和取消赞效果
- DevExpress中GridControl的使用笔记(转)
- swoole扩展实现真正的数据库连接池
- EntityFramework安装失败
- 异步 Apex 类
- s - t 平面图最大流 (附例题 bzoj 1001)
- UVALive 7143 Room Assignment(组合数学+DP)
- openstack网络基本概念(转)