Official

D - 植物園の保全計画 / Conservation Plan for the Botanical Garden Editorial by sounansya


まず、\(B_i\) が \(T\) 以上の植物は何もしなくても枯れないので考えなくて良いです。 \(B_i\) が \(T\) 未満の植物に対して適切に給水設備を設置することを考えます。

\(d[i][j]\) を「植物 \(i\) まで見た時にコスト \(j\) 以下で得られる鑑賞価値の総和の最大値」とした動的計画法を考えます。

\(B_i\) が \(T\) 以上なら \(d[i][j] =\max(d[i][j],d[i-1][j]+A_i)\) 、\(B_i\) が \(T\) 未満なら \(d[i][j] =\max(d[i][j],d[i-1][j-C_i]+A_i)\) とした遷移を行えば良いです。

実装例(Python3)

n, m, t = map(int, input().split())
INF = 10**18
d = [-INF] * (m + 1)
d[0] = 0
for i in range(n):
    dd = d.copy()
    a, b, c = map(int, input().split())
    if b >= t:
        for j in range(m + 1):
            dd[j] = max(dd[j], d[j] + a)
    else:
        for j in range(c, m + 1):
            dd[j] = max(dd[j], d[j - c] + a)
    d = dd
print(max(d))

この遷移は in-place(配列を使い回す)に行うことも可能です。

実装例(Python3)

n, m, t = map(int, input().split())
INF = 10**18
d = [-INF] * (m + 1)
d[0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    if b >= t:
        for j in range(m + 1):
            d[j] += a
    else:
        for j in range(m, c - 1, -1):
            d[j] = max(d[j], d[j - c] + a)
print(max(d))

posted:
last update: