Edit

【pythonでABC175を解説】E - Picking Goods

問題概要

問題ページ

E - Picking Goods
E - Picking Goods

問題ページへ移動する

問題文

\(R\) 行 \(C\) 列に並んだマス目に \(K\) 個のアイテムが置いてあります。\(1 \leq i \leq R\) 行目、 \(1 \leq j \leq C\) 列目のマスを \((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\)
  • 入力は全て整数である

問題の考察

ACコード

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    r, c, k = list(map(int, readline().split()))
    ls = [[0] * c for _ in range(r)]
    for i in range(k):
        rv, cv, kv = list(map(int, readline().split()))
        ls[rv-1][cv-1] += kv
    if c == 1:
        t = 0
        for j in range(r):
            t += ls[j][0]
        print(t)
        exit()
    else:
        pre = [0] * c
        for i in range(r):
            dp = [[0] * 4 for _ in range(c)]
            for j in range(c - 1):
                dp[j][0] = max(pre[j], dp[j][0])
                dp[j][1] = max(pre[j] + ls[i][j], dp[j][1])
                dp[j + 1][0] = max(pre[j + 1], dp[j + 1][0])
                dp[j + 1][1] = max(pre[j + 1] + ls[i][j + 1], dp[j + 1][1])
                for k in range(2, -1, -1):
                    dp[j + 1][k + 1] = max(dp[j][k] + ls[i][j + 1], dp[j + 1][k + 1], dp[j][k + 1])
            pre = [max(dp[j]) for j in range(c)]
        print(max(dp[-1]))


if __name__ == '__main__':
    solve()

-Edit
-