← 返回题目列表

AtCoder · abc369_f

I. 收集硬币

中文机器翻译题面 查看原题

分数: 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