atcoder ABC 317 D - Presidentの勉強

DP atcoder

atcoder.jp

・参考
Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)

・説明
　参考にも書いてあるが、ナップサック問題のDPと同じように解ける。dp[n]はn議席獲得するために必要な鞍替えさせる最低限の人の数である。
　今回は鞍替えさせる人数をコストwと見てこれを最小にすることを考える。コストwはX[i]>Y[i]のとき鞍替えさせる必要がないので0、X[i]

#入力。
n=int(input())
X=[]
Y=[]
Z=[]
s=0
for _ in range(n):
  x,y,z=map(int, input().split())
  X.append(x)
  Y.append(y)
  Z.append(z)
  s+=z

#dp=[10**18]*(s+1)
dp=[10**18 for _ in range(s+1)]
dp[0]=0
#print(dp)

for i in range(n):
  #コストを決める。
  if X[i]>Y[i]:
    w=0
  else:
    w=(Y[i]-X[i]+1)//2

  #dpの遷移。ナップサック問題みたく。
  j=s
  while j>=Z[i]:
    dp[j]=min(dp[j],dp[j-Z[i]]+w)
    #print(j,dp[j])
    j-=1
#print(dp)

#出力。
ans=10**18
for i in range((s+1)//2,s+1):  
  ans=min(ans,dp[i])
print(ans)