E - 选取物品

得分：500点

问题描述

在一个$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个物品。可以忽略经过的方格上的物品。

找出他可以拾取的物品价值的最大总和。

约束条件

• $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$

输出

打印高桥可以拾取物品的最大总价值。

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

8

他有两种到达终点的方式：

• 按照顺序访问$(1, 1), (1, 2), (2, 2)$。在这种情况下，他可以拾取的物品的总价值为$3 + 5 = 8$。
• 按照顺序访问$(1, 1), (2, 1), (2, 2)$。在这种情况下，他可以拾取的物品的总价值为$3 + 4 = 7$。

因此，他可以拾取的物品的最大总价值为$8$。

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

29

在第一行有四个物品。最优选择如下：

• 按照顺序访问$(1, 1), (1, 2), (1, 3), (1, 4), (2, 4), (2, 5)$，并拾取除了$(1, 2)$上的物品之外的所有物品。这样，他可以拾取的物品的总价值为$3 + 4 + 2 + 20 = 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