「JOISC 2019 Day2」Two Dishes

· · 题解

赛前写题解增加 rp。今天我的瞪代码补题法被 calvin 瑞平为【】式学习法了，但是菜菜的我除了这个也不会别的了，所以整个理解都是瞪着题解代码 yy 出来的，有很大概率出错。 从考场部分分的角度来理解这个思路。以下默认 n,m 同阶，有的复杂度直接都按照 n 写了。

我是普及组小朋友，我会 \mathcal{O}(nm) dp！考虑设 f_{i,j} 表示当前选了 a_{1\sim i},b_{1\sim j} 可以产生的最大贡献值，转移显然是单次 \mathcal{O}(1)，因为只需要枚举目前这一次选 a_{i+1} 还是 b_{j+1} 就可以了。显然不太能优化啥的，毕竟这个状态维度降不下去。

我是 AT 战神，我精通格路模型！发现走 a_{i+1},b_{j+1} 可以看作相对独立的两维，所以考虑转化为格路，选择 a 看作向右走一格，选 b 看作向上走一格，那么相当于要求出一条从 (0,0) 到 (n,m) 的符合条件的最大权值路径。

我是数据结构萌新，我不会颜色段均摊也不会写 ODT！所以不考虑 p,q\ge 1 的特殊部分分，直接想怎么把限制转化到网格图上。联系一下某个看起来很水的部分分：s_1=s_2=\cdots=s_n=t_1=t_2=\cdots=t_m，做法就是发现在 s 之前选出的 a,b 肯定各是一段前缀，考虑枚举 a 中选出的那一段前缀 1\sim i，然后肯定可以直接得到 b 选出的是哪一段前缀，用指针可以做到 \mathcal{O}(n+m)。虽然这个部分分看起来很鸡肋，但是它倒是给了正解做法一点小启发：考虑如果我们希望在选 a_i 时可以拿下 p_i 的贡献，能直接求出一个 j 表示如果要拿下 p_i，在填 a_i 之前至多选 b 的前缀到 b_j（这个 j 很好求，其实就是满足 \sum\limits_{k=1}^i a_k+\sum\limits_{k=1}^j b_k\le s_i 的最大 j），也就是说我们的格路一定要在点 (i,j) 之下。同理地，对于每个 b_i，设 j 为满足 \sum\limits_{k=1}^j a_k+\sum\limits_{k=1}^i b_k\le t_i 的最大数，那么格路一定要在 (j,i) 之上。

也就是说我们把权值的计算转化为“满足某个条件就可以获得该权值”，然后把这个条件扔到了网格上。设对于每个 a_i 求出的限制 c_i=j+1，对于每个 b_i 求出的限制 d_i=j+1，那么相当于格路一定要在每个 (i,c_i) 之上（可以恰好经过）就能得到 p_i，每个 (d_i,i) 之下（可以恰好经过）就能得到 q_i。把两个限制转化为同一种形式，先给答案加上 p_i，然后变成两种点，格路在 (i,c_i) 之下就能得到 -p_i，格路在 (d_i,i) 之下就能得到贡献 q_i，最大化格路的总权值。

我切穿 AT 的 dp 系列题，我擅长一切 dp 以及其状态优化！先设一个很劣的状态 f_{i,j} 表示当前格路走到点 (i,j) 的最大权值，考虑 f_{i-1}\to f_i。分为两步，f_{i-1,j}\to f_{i,j}，那么加上在 (i,j) 之下包住的所有点权值即可；然后 f_{i,j-1}\to f_{i,j}（这个按照纵坐标从小到大顺次转移），发现不需要加额外权值。前者相当于枚举所有在第 j 列的点，它们的权值对 f_i 做一个后缀加，而后者相当于 f_i 每一项都做前缀 checkmax。试着维护 f_i 的差分，那么一次后缀加可以这样理解（任何情况下，只要 checkmax 没有遗漏，差分数组都是非负的）：

如果后缀加 (x,w)，w\ge 0，那么只会影响到至多一个点的 diff 值（因为后缀都会直接一样地改，diff 不会变），此时暴力维护这个 diff 的变化就是了。

如果 w<0 呢？

那么发现暂时地，一段区间 [x,y) 内的 f 值仍然会取一个原先的未受 w 影响的最大值，此时会导致 diff_{x\sim y-1} 都被推平成 0。（写到这里突然感觉非常地颜色段均摊啊！p,q\ge 1 的颜色段均摊做法是不是一个意思？）然而到了一个点 y，w+\sum\limits_{i=x}^{y} diff_i\ge 0，这其实就是新的 f_y-f_{x-1}，此时 f_{x-1} 是 f_{x\sim y-1} 中的前缀 \max，而 f_y-f_{x-1}\ge 0 说明 f_y 成为了一个更大的取值，更新了 f 值，之后的 diff_{y+1\sim m} 仍然不会改变。而这样以来，我们只需要把 diff_{x\sim y-1} 推平成 0，diff_y=w+\sum\limits_{i=x}^{y} diff_i，后面的不用变。被推平的那一段我们直接把它整个缩到 y-1 这个位置上，如果能保证依次插入的 w 单调不增，那么就可以保证推平的这一段以后不会再分裂了。所以 w<0 时，每次在去掉至少一个现在已经变成 0 了的差分项，至多再加入一个新的差分项，维护 dp 的总复杂度 \mathcal{O}(n+m)（因为有效的后缀加的点至多 n+m 个，然后只有在每次后缀加的时候才需要更新 diff），然后再加上一开始二分找 c_i,d_i，总复杂度 \mathcal{O}((n+m)\log n)，当然指针也可以做到线性，不过区别不大了。

整个过程下来我认为比较流畅，只要像我一样不会颜色段均摊就能比较自然地推到这个正解，过程中也解释了 p,q\ge1 中颜色段均摊在正解做法中的体现（？我不知道是不是哈，纯属我感性理解），这个题给了我关于格路模型的很大启发，也有一种做题方式的体现：想不通可以手模画点图的。只是希望能以这个过程为自己在省选赛场上解题做一个示范吧。

Submission.