Official
D - 植物園の保全計画 / Conservation Plan for the Botanical Garden Editorial
by
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)\) とした遷移を行えば良いです。
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(配列を使い回す)に行うことも可能です。
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:
