分数: 500 点
问题陈述
有 K 物品放置在正方形网格上 R 行和 C 列。让 (i, j) 表示位于 i- 第行 (1 \leq i \leq R)和 j- 第列 (1 \leq j \leq C)。的 i- 第一项位于 (r_i, c_i) 并且具有值 v_i.
高桥将于 (1, 1),开始,然后到达 (R, C),目标。当他在 (i, j),他可以移动到 (i + 1, j) or (i, j + 1) (但不能移动到不存在的方格)。
他可以在他访问的方格上拾取物品,包括起点和终点,但每行最多三个。允许忽略他访问的广场上的项目。
找出他拾取的物品价值的最大可能总和。
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
R C K r_1 c_1 v_1 r_2 c_2 v_2 : r_K c_K v_K
输出
打印高桥拾取的物品的最大可能值总和。
示例输入 1
2 2 3 1 1 3 2 1 4 1 2 5
示例输出 1
8
他有两种方法可以达到目标:
- 访问 (1, 1), (1, 2),和 (2, 2),按此顺序。在这种情况下,他可以拾取的物品的总价值是 3 + 5 = 8.
- 访问 (1, 1), (2, 1),和 (2, 2),按此顺序。在这种情况下,他可以拾取的物品的总价值是 3 + 4 = 7.
因此,他拾取的物品价值的最大可能总和是 8.
示例输入 2
2 5 5 1 1 3 2 4 20 1 2 1 1 3 4 1 4 2
示例输出 2
29
我们有四件商品 1-st 行。最优选择如下:
- 访问 (1, 1) (1, 2), (1, 3), (1, 4), (2, 4),和 (2, 5),按此顺序,拾取除上面的一项之外的所有项目 (1, 2)。那么,他拾取的物品的总价值将是 3 + 4 + 2 + 20 = 29.
示例输入 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