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$ $\vdots$ $R_N$ $C_N$

输出格式

输出两行。 第一行应包含你最多可以拾取的硬币数。 第二行应包含一条达到该最大值的路径，作为长度为 $H+W-2$ 的字符串。 该字符串的第 $i$ 个字符应为 $D$，若第 $i$ 步为向下移动；若为向右移动，则为 $R$。 如果存在多条使拾取硬币数最大化的路径，你可以输出其中任意一条。

3 4 4
3 3
2 1
2 3
1 4

3
DRRDR

2 2 2
2 1
1 2

1
DR

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

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)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$，你可以在 $(2,1),(2,3),(3,3)$ 处拾取三枚硬币。
路径 $RD$ 也是可以接受的。

标签: AtCoder|abc369F

来源

AtCoder|abc369F