AT_abc175_e [ABC175E] Picking Goods

题目描述

在一个有 $R$ 行 $C$ 列的网格中，放置了 $K$ 个物品。用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子，第 $i$ 个物品位于格子 $(r_i, c_i)$，其价值为 $v_i$。

高桥君从格子 $(1, 1)$ 出发，移动到终点格子 $(R, C)$。当高桥君处于格子 $(i, j)$ 时，可以移动到（如果存在的话）格子 $(i+1, j)$ 或格子 $(i, j+1)$。

高桥君可以拾取经过的格子（包括起点和终点）上的物品。但在同一行中，最多只能拾取 $3$ 个物品。如果经过的格子上有物品，也可以选择不拾取。

请你求出高桥君能够拾取的物品价值之和的最大可能值。

输入格式

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

$R$ $C$ $K$
$r_1$ $c_1$ $v_1$
$r_2$ $c_2$ $v_2$
$\vdots$
$r_K$ $c_K$ $v_K$

输出格式

输出高桥君能够拾取的物品价值之和的最大可能值。

输入输出样例 #1

输入 #1

2 2 3
1 1 3
2 1 4
1 2 5

输出 #1

8

输入输出样例 #2

输入 #2

2 5 5
1 1 3
2 4 20
1 2 1
1 3 4
1 4 2

输出 #2

29

输入输出样例 #3

输入 #3

4 5 10
2 5 12
1 5 12
2 3 15
1 2 20
1 1 28
2 4 26
3 2 27
4 5 21
3 5 10
1 3 10

输出 #3

142

说明/提示

限制条件

• $1 \leq R, C \leq 3000$
• $1 \leq K \leq \min(2 \times 10^5, R \times C)$
• $1 \leq r_i \leq R$
• $1 \leq c_i \leq C$
• $(r_i, c_i) \neq (r_j, c_j)\ (i \neq j)$
• $1 \leq v_i \leq 10^9$
• 所有输入均为整数

样例解释 1

有以下两种移动方式：

• 按顺序经过格子 $(1, 1)$、$(1, 2)$、$(2, 2)$，此时可拾取的物品价值之和为 $3 + 5 = 8$。
• 按顺序经过格子 $(1, 1)$、$(2, 1)$、$(2, 2)$，此时可拾取的物品价值之和为 $3 + 4 = 7$。

因此，高桥君能够拾取的物品价值之和的最大可能值为 $8$。

样例解释 2

第 $1$ 行有 $4$ 个物品。最优的拾取方式如下：

• 按顺序经过格子 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 4)$、$(2, 5)$，其中只不拾取格子 $(1, 2)$ 上的物品，物品价值之和为 $3 + 4 + 2 + 20 = 29$。

由 ChatGPT 4.1 翻译