AT_abc369_f [ABC369F] Gather Coins

题目描述

有一个高 $H$ 行、宽 $W$ 列的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

在这个网格上有 $N$ 枚硬币，第 $i$ 枚硬币可以通过经过格子 $(R_i,C_i)$ 来捡到。

你的目标是从格子 $(1,1)$ 出发，每次只能向下或向右移动一格，尽可能多地捡到硬币，最终到达格子 $(H,W)$。

请你求出最多可以捡到多少枚硬币，并输出一种能够达到这个最大值的移动路径。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$ $N$ $R_1$ $C_1$ $R_2$ $C_2$ $\cdots$ $R_N$ $C_N$

输出格式

输出两行。第一行输出你最多可以捡到的硬币数量。第二行输出一种能够实现该最大值的移动路径，用一个长度为 $H+W-2$ 的字符串表示。第 $i$ 个字符表示第 $i$ 次移动，若向下移动则为 D，若向右移动则为 R。

如果存在多条能够捡到最多硬币的路径，输出其中任意一条均可。

输入输出样例 #1

输入 #1

3 4 4
3 3
2 1
2 3
1 4

输出 #1

3
DRRDR

输入输出样例 #2

输入 #2

2 2 2
2 1
1 2

输出 #2

1
DR

输入输出样例 #3

输入 #3

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1

输出 #3

5
DRRRRRRRRDDDDDRRDRDDRRR

说明/提示

限制条件

• $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)$ 互不相同
• 输入均为整数

样例解释 1

如上图所示，按照 $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$ 的路径移动，可以捡到 $(2,1)$、$(2,3)$、$(3,3)$ 这三个格子的硬币。

样例解释 2

RD 这样的移动路径也是正确答案。

由 ChatGPT 4.1 翻译