YZOJ P3791 餐馆

YZOJ P3791 餐馆

时间限制:2000MS      内存限制:524288KB

难度:\(6.0\)

  • 题目描述

在一条东西向的街道上有 \(n\) 个餐馆,从西向东编号为 \(1\) 至 \(n\),第 \(i\) 个餐馆和第 \(i+1\) 个餐馆的距离为 \(a_i\) 。

吃货小W喜欢到这条街道的餐馆里吃饭。现在,小W得到了 \(m\) 张餐票,每张餐票可以用于在街道上的任一餐馆里吃一餐。在第 \(i\) 个餐馆中,使用第 \(j\) 张餐票吃饭,可以获得的美味度为 \(b_{i,j}\) 。注意,每张餐票最多用一次,但在同一餐馆内可以使用任意多张餐票。

小W打算用完这 \(m\) 张餐票。他可以选择任一餐馆作为起点,每次吃饭时,可以选择一个餐馆,然后从当前位置(上次吃饭的地点,如果不存在则为起点)出发前往该餐馆并用任意一张未用过的餐票吃一餐,直到吃完 \(m\) 餐为止。小W希望最大化每次吃饭的美味度之和减去路上经过的总路程的值。

  • 输入格式

输入第一行包含两个正整数 \(n,m\) 。

第二行包含 \(n-1\) 个正整数 \(a_1,a_2,\cdots,a_{n-1}\) 。

接下来 \(n\) 行,每行包含 \(m\) 个正整数,其中第 \(i\) 行第 \(j\) 个数为 \(b_{i,j}\) 。

  • 输出格式

输出一行一个整数,表示所求的最大值。

  • 样例输入

  • 样例输出

  • 样例说明

最优方案如下:以餐馆 \(1\) 为起点,在餐馆 \(1\) 使用第 \(1\) 张餐票、第 \(3\) 张餐票,然后前往餐馆 \(2\) 使用第 \(2\) 张餐票、第 \(4\) 张餐票。

  • 数据规模与约定

对于所有数据,\(nm \leq 10^6\),\(n \geq 2\),\(a_i, b_{i, j} \leq 10^9\) 。

 

 

 

Source:ARC067 F – Yakiniku Restaurants,数据范围有改动(加强)


 

 

 

注意到(很显然爆零的我没有注意到)最优解肯定是在一段区间内,所以有

\(f_{l, r}=\sum\limits_{j=1}^m{\max\limits_{i=l}^r{b_{i, j}}} – \sum\limits_{i=l}^{r-1}a_i\)

直接 \(O(n^2)\) 枚举 \((l, r)\) , RMQ \(O(m)\) 转移,暴力总复杂度 \(O(n^2m)\) 。

考虑优化,这里有两种办法:

法1,转换问题,对于每个 \((l, r)\) 区间寻找最优的 \(b_{i, j}\) 转化为 对于每个 \(b_{i, j}\) 寻找它能贡献的 \((l, r)\) 区间。对于一个 \(b_{i, j}\) ,很明显它能贡献的区间为 \((\)它左边第一个不比它小的数\(,\)它右边第一个比它大的数\()\) (既不重复也不漏算),这个过程可以用笛卡尔树维护(我也不知道为什么dalao们都用笛卡尔树(果然我不是dalao))两次单调栈维护,值得注意的是正反的两个单调栈有且只有一个必须加等号

发现可以把这一的贡献关系表示成 \(l\) 为横坐标 \(r\) 为纵坐标的坐标系 中的一些矩形,增加贡献区间就相当于矩形覆盖。即每次对于一个 \(l\) ,在所有包含 \(l\) 的贡献组成的平面中,找到权值最大的一个点(它的纵坐标相当于 \(r\)),用它来贡献 \(f_{l,}\) 。注意到这个过程可以使用扫描线(按 \(l\) 从小到大扫描)+线段树维护(扫到 \(l\) 时合法矩形中点的点权最大值),时间复杂度 \(O\left(nm \log \left(nm\right)\right)\) 。

 

 

 

 


法2,注意到若 \(f_{l, }\) 的最优贡献点在 \(k\) ,那么 \(f_{l+1, }\) 的最优贡献点一定不会在 \(k\) 之前,即决策单调性证明自行感性理解(其实是我不会证)。所以分治一下即可,以 \(mid\) 为 \(l\) 时最优的 \(r\) 可能在 \([kl, kr]\) 中,时间复杂度 \(O\left(nm \log n\right)\) 。

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注