ABC431 D – Robot Customize

D - Robot Customize

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

ロボットの頭と体に部品を取り付けられる。頭と体に取り付けるときにそれぞれ異なる嬉しさがあり、その嬉しさが最大になるように部品を取り付ける問題。ただしそれぞれの部品には重さがあり、体より頭が重くなってはいけない。

まず全ての部品を体につけることを想定して、嬉しさの合計を算出する。・・・sb

この時点では部品が全て体についているので、当然頭より体の方が重い。

それぞれの部品を頭に付け替えた時の価値（どのくらい嬉しさが上昇するか）を各部品ごとに重さと合わせて保持しておく。・・・wv（この時嬉しさが上昇しないものは意識しなくて良い）

ここからDPを書いていく。

横に重さ、縦に処理する部品の数（wv）の2次元配列を作る。スタートだけ0にする。

-1以外のところを処理していく。

• 1つ目の部品が重さ2、価値が30とすると
  • 選ばない場合は重さは変わらず0、価値も変わらず0
  • 選ぶ場合は重さ2のところに価値が30プラスされる

以下のようになる。

2つ目の部品は重さ8、価値が4。

重さは頭より体の方が重くないといけないので全体の重さの合計÷2より大きくなる場合は選択できない。

上の表の重さ0と2のどちらも8を足すと全体の重さの合計÷2より大きくなってしまうので、8の部品は選ぶことができない。

部品を選ばない場合価値は変わらないので、以下のようになる。

あとは上の表の最後の行からmaxの値を取得して、全ての部品を体につけた時の嬉しさに頭に部品を付け替えた時の価値を足せば答えになる。

以下でACできた。

def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

n = int(input())

sw = 0
sb = 0

wv = []
for i in range(n):
  w, h, b = i_map()
  sw += w
  sb += b
  if h > b:
    wv.append((w, h-b))

n = len(wv)
sw //= 2
dp = [[-1]*(sw+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(len(wv)):
  w, v = wv[i]
  for j in range(sw+1):
    if dp[i][j] == -1: # -1は処理しない
      continue
    dp[i+1][j] = max(dp[i+1][j], dp[i][j]) # 選ばない場合
    if j+w <= sw: # 重さが半分以下ならOK
      dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v) # 選ぶ場合

ans = 0
for i in range(sw+1):
  ans = max(ans, dp[n][i])
print(sb + ans)
Code language: Python (python)