分数: 500 点
问题陈述
有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
有 N 此网格上的硬币,以及 i-第枚硬币可以通过单元格拾取 (R_i,C_i).
您的目标是从单元格开始 (1,1),重复向下或向右移动一个单元格,并到达单元格 (H,W) 同时捡起尽可能多的硬币。
找到您可以拾取的最大硬币数量以及达到此最大数量的路径之一。
约束
- 2\leq H,W \leq 2\times 10^5
- 1\leq N \leq \min(HW-2, 2\times 10^5)
- 1\leq R_i \leq H
- 1\leq C_i \leq W
- (R_i,C_i)\neq (1,1)
- (R_i,C_i)\neq (H,W)
- (R_i,C_i) 成对不同。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W N R_1 C_1 R_2 C_2 \vdots R_N C_N
输出
打印两行。
第一行应包含您可以拾取的最大硬币数量。
第二行应包含达到此最大值的路径之一(作为长度的字符串) H+W-2。
的 i该字符串的第一个字符应该是 D 如果 i第一次移动是向下的,并且 R 如果它是向右的。
如果有多个路径可以最大化拾取的硬币数量,您可以打印其中任何一个。
样本输入 1
3 4 4 3 3 2 1 2 3 1 4
示例输出 1
3 DRRDR

如上图所示,通过移动 (1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4),您可以在以下位置拾取三枚硬币 (2,1),(2,3),(3,3).
示例输入 2
2 2 2 2 1 1 2
示例输出 2
1 DR
路径 RD 也是可以接受的。
示例输入 3
10 15 8 2 7 2 9 7 9 10 3 7 11 8 12 9 6 8 1
示例输出 3
5 DRRRRRRRRDDDDDRRDRDDRRR