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$ 。

 

 

 …