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\) 。

 

 

 …