CF1423M Milutin's Plums
约瑟夫用脑玩
·
·
题解
一些定义
1D/1D 方程：f_i=\min_{j<i}g_j+w_{j,i}
最优决策：不妨设为 ps_i<i，满足 f_i=g_{ps_i}+w_{ps_i,i}。
决策单调性：\forall i<n,ps_i\le ps_{i+1}。
以上和本题没有太大关系。
对于矩阵 A 定义 pos_i=\{j|\forall p,A_{j,i}\le A_{p,i}\}。
单调矩阵：满足 \forall i<j,pos_i\le pos_j 的矩阵 A。
完全单调矩阵：满足任意一个子矩阵均为单调矩阵的矩阵 A。
子矩阵：对于行集合 i_1,i_2,\cdots,i_n 和列集合 j_1,j_2,\cdots,j_m，仅保留 x\in\{i\},y\in\{j\} 的元素 A_{x,y} 所形成的矩阵。
性质：完全单调矩阵的子矩阵还是完全单调矩阵。
可能是正文
一般的 1D/1D 可以通过令 A_{i,j}=g_j+w_{j,i}，f_i=A_{pos_i,i} 从而套用下述算法。
不难发现题目给出条件即为完全单调矩阵的定义，我们只要求出 \{pos\} 即可在 n 次询问内给出回答，事实上，在求出 pos 的过程中可以记录下本题的答案。
求出一个完全单调矩阵的 pos 数组，可以使用 SMAWK 算法。（读音同：smoke 算法）
简单分治
我们取出奇数列，递归求出它们的 pos，递归到底层只有一行时暴力求出 pos 并返回。
则对于偶数列的决策 pos_{2k} 可以通过遍历 i\in[pos_{2k-1},pos_{2k+1}] 来解决，复杂度是 O(t\times(pos_{n+1}-pos_0)=tn)，其中 t 为递归层数，显然为 \log_2n。
优化
每列只需要一个 pos，若我们将 n\times n\to \frac n2\times n\to\frac n4\times n\to\cdots 的矩阵传下去，发现第二维有许多元素无用。
利用完全单调矩阵的性质，我们有如下结论：
A_{i_1,j}<A_{i_2,j}\to pos_{i_2}\neq\{A_{i_2,c}|1\le c\le j\}
A_{i_1,j}\ge A_{i_2,j}\to pos_{i_1}\neq\{A_{i_1,c}|j\le c\le n\}
这里 \neq 非严谨的定义为除去后还存在位置满足 pos 的定义。
根据此性质我们设计如下过程，定义 Del(i) 为去除第 i 行：
- 初始位置在 (1,1)，当前位置在 (i,i)。
- 比较 A_{i,i},A_{i,i+1}：
- 若 A_{i,i}\ge A_{i,i+1}，则 Del(i)。
- 若 i\neq 1，则 i-1\to i。
- 若 A_{i,i}<A_{i,i+1}：
- 若 i=n，则 Del(n+1)。
- 若 i\neq n，则 i+1\to i。
这个过程被称之为 Reduce 操作，将其在每次递归取奇数行前调用即得到了 SMAWK 算法。
实现
我怎么能公然说我的实现好呢？
我的实现和其他人不一样，主要体现在：
由于本题卡交互次数代码已经被改的面目全非，有需要的找我，我可以据情况友情提供帮助。
提供代码，含注释。
实际上，只要 Reduce 操作对了，删除真的删掉了，遍历 [pos_{2k-1},pos_{2k+1}] 也没写错，这算法必定是线性的。
剩下的就是卡次数，给出两点需要注意的地方：
-
- 最后的 pos 不用重新询问，在处理过程中时刻更新答案，少一倍次数。
正着 Reduce 两倍次数，反着处理偶数列一倍次数，剩下的一倍次数我用来重新询问（这大概就是我 nt 的地方
CF 评测系统上超过次数为 TLE，除非手动返回，否则不给提示信息，这是我没想到的。