题目详情题解（0）讨论（0）提交记录（0）

AT_abc175_e.[ABC175E] Picking Goods

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个有 RR 行 CC 列的网格中，放置了 KK 个物品。用 (i,j)(i, j) 表示第 ii 行第 jj 列的格子，第 ii 个物品位于格子 (ri,ci)(r_i, c_i)，其价值为 viv_i。

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

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

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

输入格式

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

RR CC KK
r1r_1 c1c_1 v1v_1
r2r_2 c2c_2 v2v_2
⋮\vdots
rKr_K cKc_K vKv_K

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    8

  • 输入#2

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

    输出#2

    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

说明/提示

限制条件

  • 1≤R,C≤30001 \leq R, C \leq 3000
  • 1≤K≤min⁡(2×105,R×C)1 \leq K \leq \min(2 \times 10^5, R \times C)
  • 1≤ri≤R1 \leq r_i \leq R
  • 1≤ci≤C1 \leq c_i \leq C
  • (ri,ci)≠(rj,cj) (i≠j)(r_i, c_i) \neq (r_j, c_j)\ (i \neq j)
  • 1≤vi≤1091 \leq v_i \leq 10^9
  • 所有输入均为整数

样例解释 1

有以下两种移动方式：

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

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

样例解释 2

第 11 行有 44 个物品。最优的拾取方式如下：

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页