劲爆会员制餐厅题

KingPowers · 2025-08-06 08:29:10 · 题解

Part 1. 确定 A 和 K 时的做法

我们先假设 A 序列是确定的，考虑如何设计出来求一个 f(A,B,K) 的算法。

假设选好了要为哪 K 个人服务，应该按照什么样的顺序去服务？结论是会按照 B_i 从大到小的顺序。证明考虑邻项交换，对于两个人 i,j 且 B_i<B_j，先服务 i 的答案是 \max(A_i+B_i,A_i+A_j+B_j)，而先服务 j 的答案是 \max(A_j+B_j,A_j+A_i+B_i)，显然后者不会比前者大。

假设确定为 p_1,p_2,\ldots,p_k 服务（这里假设已经是按照 B_i 从大到小排序好的顺序），则答案显然为：

\max_{i=1}^K(B_{p_i}+\sum_{j\le i}A_{p_j})

这个式子其实可以写成：

A_{p_1}+\max(B_{p_1},A_{p_2}+\max(B_{p_2},\ldots))

所以初始令 ans=0，从 i=K 开始倒着扫，每次做 ans\leftarrow A_{p_i}+\max(ans,B_{p_i}) 即可。

以上的讨论都是基于 K 个人确定的情况，现在我们可以尝试设计一个 DP 来选择这 K 个人到底是哪些了。注意到上面求答案的过程是倒着扫的，所以现在把所有的 B_i 从小到大排序。设 f(i,j) 表示前 i 个数里选了 j 个的最小答案，转移就是：

f(i,j)=\min(f(i-1,j),A_i+\max(B_i,f(i-1,j-1)))

这个 DP 直接做是 O(N^2) 的，而且后面计数的时候好像不好直接把它变成 DP 套 DP，所以我们需要对它再尝试优化下。

发现比较烦人的是后面的 \max 那项，尝试观察一下。发现对于 f(i-1,j)\le B_i 的 j，转移后仍然满足 f(i,j)\le B_i，且显然这种 j 是一段前缀。更进一步发现这些 j 处的值在以后的转移中再也不会被更新，可以直接提前计入答案！所以我们把这段前缀的值直接删去，就能砍掉转移式里的 \max 了。

重新看下现在的式子：

f(i,j)=\min(f(i-1,j),A_i+f(i-1,j-1))

这个形式可太熟悉了，一脸 slope trick 的感觉！容易归纳证明这个 DP 数组现在每一维都是下凸的了（现在不妨认为 f(i-1,0)=B_i），即差分数组是单调的，所以直接开个小根堆维护差分数组，上面的式子相当于扔一个 A_i 进去。

当然我们还要支持前面的删去值不超过 B_i 的前缀那个操作，所以现在的完整流程大概是这样的：

初始时开一个小根堆 Q，Q 内初始时只有一个元素 \infty（因为除了 f(0,0) 初值就应该是 \infty），并维护答案 ans，初始为 0。
扫描 i=1,2,\ldots,N，扫到一个 i 时，顺次执行以下操作：
- 当 ans 加上堆顶元素不超过 B_i 时，不断弹出堆顶元素并令 ans 加上它。
- 将堆顶的元素减少 B_i-ans，再将 ans 赋值成 B_i（也就是将差分数组第 0 项变成 B_i）。
- 将 A_i 加入堆中。

为了方便，可以再添加一个 B_{N+1}=\infty 并扫到 N+1。

答案是什么？根据前面的流程，我们每弹出一次堆顶（也就是在前缀删一个数）就能确定一个 j 的取值，所以当我们总共弹了恰好 K 次堆顶时，ans 就是最后的答案。

因此当 A,B,K 都确定时，我们有一个 O(N\log N) 求出 f(A,B,K) 的算法。

值得一题的是直接从反悔贪心的角度好像也能得到上面的这一流程，限于本人水平暂时不展开篇幅。

Part 2. DP 计数

下一步就是对上面的 slope trick 的过程设计 DP 计数，类似题目有 AGC049E。

为了方便，我们规定当小根堆内有相同的数时，先加入堆的数更小，这样显然不会影响答案。

考虑直接用 DP 去维护上面的小根堆。看上去上面的过程其实很复杂，由于不可能做到记录堆里面目前有啥，所以好像也无法得知每次弹出的数具体是什么。但是我们可以直接钦定每个 A_i 最后有没有被弹出，如果钦定了一个 A_i 被弹出限制就是以后压入比 A_i 更小的数时也一定会一起弹出，钦定不被弹出同理。所以可以这么设计状态：令 dp(i,j,L,R,ans) 表示当前考虑了前 i-1 个数，钦定了 j 个数最后被弹出，以后加入 <L 的数必须被弹出，\ge R 的数不能被弹出，目前答案是 ans 的方案数。

转移个人觉得其实是容易的，但还是稍微展开讲一下。

首先考虑执行上面的弹出堆顶的操作，这里需要简单分类讨论下：

如果 ans\le b_i，则我们之前钦定要被弹出的数在这里会全部被弹走，现在堆顶会剩下钦定没被弹的最小的数，它会减去 B_i-ans。所以此时执行 l\leftarrow 0,r\leftarrow r-B_i+ans,ans\leftarrow B_i。
否则说明之前钦定要被弹出的数在这里弹不完，要留到以后再弹，堆顶会有一个钦定被弹的数变成 ans-B_i。所以此时执行 l\leftarrow\min(l,ans-B_i) 即可。

现在得到了弹出堆顶后新的 l,r,ans，枚举当前 a_i 的值再更新变量转移即可。

直接实现上面的 DP 过程复杂度是 O(N^3V^4) 的，看上去很爆但其实常数很小，简单卡常即可通过。不过再简单前缀和优化一下就能做到 O(N^3V^3) 了。

事实上本题可以做到 O(N^3V^2)，水平所限不再展开篇幅。

代码和其它题解基本差不多，就不放了。