YZOJ P2384 Naive – DP II

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

 

 

 

 

发表回复

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