← 返回题目列表

AtCoder · abc175_e

E. 拣货

中文机器翻译题面 查看原题

分数: 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