YZOJ P2384 Naive – DP II

时间限制：2000MS 内存限制：768KB

难度：\(5.0\) 出题人：lightning

• 题目描述

请注意不寻常的空间限制。

由于空间的限制，无法直接给出每个位置的金币数量，所以需要用一种新的方法来得到金币的数量——定义长度为 \(P\) 的数组 \(P\) 和长度为 \(T\) 的数组 \(T\)，棋盘 \((i,j)\) 上的金币数量为 \((P_i+T_j) \bmod Mod\) 。

• 输入格式

第一行输入三个整数，\(P\)、\(T\)、\(Mod\) 。

第二行输入 \(P\) 个整数，表示数组 \(P\) 。

第三行输入 \(T\) 个整数，表示数组 \(T\) 。

• 输出格式

输出包括两行——

第一行输出一个整数表示获得的最多的金币数。

第二行输出方案，方案用一个只包含 \(P\) 和 \(T\) 的字符串表示，\(P\) 表示向下、\(T\) 表示向右。

• 样例输入

• 样例输出

• 数据规模与约定

对于 \(30\%\) 的数据，\(P, T \leq 100\) 。

对于 \(100\%\) 的数据，\(P, T \leq 5000，Mod \leq 100000\) 。

 

 

 

---

 

 

 

可以把动态规划的数组 \(f_{i, j}\) 分成两部分，从起点和终点都分别向中间进行 DP 找出最小值，最后在中间寻找最小的一个点使左右（上下）两部分的和最小，对它继续进行转移。

也就是说把 \((x_1, y_1)\) ~ \((x_2, y_2)\) 这个矩阵分成两个子矩阵 \((x_1, y_1)\) ~ \((\lfloor\frac{x_1+x_2}{2}\rfloor, j)\) 和 \((\lfloor\frac{x_1+x_2}{2}\rfloor+1, j)\) ~ \((x_2, y_2)\) ， \(j\) 是使得这两个子矩阵分别正向DP的 \(f\) 和反向DP的 \(f’\) 使得 \(f_j+f’_j\) 最大的列编号。

因为正向DP表示从第一个子矩阵左上方到右下方（第 \(j\) 列）的最大金币数，反向DP表示第二个子矩阵从右下方到左上方（第 \(j\) 列）的最大金币数，它们在第 \(j\) 列可以进行合并，合并成了一条从当前矩阵的左上方到右下方的完整路径，也就代表了从 \(j\) 列走能获得的最大金币数，同时还得到了 \((mid, j)\) 的路径方向。这样就符合分治的思想——把当前这个矩阵分割成两个子矩阵，分别处理后再合并。

这样不断处理下去，最后就会得到一条从 \((1, 1)\) ~ \((N, M)\) 的完整路径，最大的金币数也能被顺便算出来。

 

幸好我弄了一份 PPT ，详细的过程都在里面了，这是下载链接。

Divide.pdf Divide.pptx