Picking Goods

题目描述

在一个有 $R$ 行 $C$ 列方格的网格上放有 $K$ 个物品。记 $(i, j)$ 为第 $i$ 行（$1 \leq i \leq R$）第 $j$ 列（$1 \leq j \leq C$）的方格。第 $i$ 个物品位于 $(r_i, c_i)$ 并且具有价值 $v_i$。 Takahashi 将从起点 $(1, 1)$ 出发，到达终点 $(R, C)$。当他位于 $(i, j)$ 时，他可以移动到 $(i + 1, j)$ 或 $(i, j + 1)$（但不能移动到不存在的方格）。 他可以捡起他经过的方格上的物品，包括起点和终点，但每一行最多捡取三个物品。经过方格上的物品也可以选择不捡。 求他能获得的物品价值总和的最大可能值。

输入格式

输入从标准输入按以下格式给出： $R$ $C$ $K$ $r_1$ $c_1$ $v_1$ $r_2$ $c_2$ $v_2$ : $r_K$ $c_K$ $v_K$

输出格式

输出 Takahashi 捡到的物品价值总和的最大可能值。

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

8

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

29

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

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, 2)$ 和 $(2, 2)$。在这种情况下，他可以捡到的物品总价值为 $3 + 5 = 8$。 按顺序访问 $(1, 1)$、$(2, 1)$ 和 $(2, 2)$。在这种情况下，他可以捡到的物品总价值为 $3 + 4 = 7$。

因此，他能捡到的物品价值总和的最大可能值是 $8$。
我们在第 $1$ 行有四个物品。最优选择如下：

按顺序访问 $(1, 1)$ $(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 4)$ 和 $(2, 5)$，并捡起除 $(1, 2)$ 上的物品以外的所有物品。此时，他捡到的物品价值总和为 $3 + 4 + 2 + 20 = 29$。

标签: AtCoder|abc175E

来源

AtCoder|abc175E