Codejam2022 Round1B: Controlled Inflation
問題
N人の顧客が持っているP個の製品に空気を入れる。各製品の空気圧に合わせるために、空気入れ装置のボタン押し下げを行う場合、全製品に空気入れを行うための押し下げ操作の最少回数は幾つになるか？ただし、顧客の順番入れ替えはNGだが、各顧客の製品並び替えはOK。また装置の初期値は０。
アルゴリズム
各顧客に対しては、昇順に入れるか、もしくは降順に入れると、最も少ない操作回数で行えそう。ただし、i+1番目の顧客に遷移するときに、i番目の顧客の最後の値との差分によっては昇順または降順のどちらが最少になるかは変わるので、昇順で遷移する場合、降順で遷移する場合をメモしながら、最終的にN番目まで終わった時に少ない方を解とする。
実装
-
dp_{i,0} -
dp_{i,1}
同じように、
-
dp_{i,0} -
dp_{i,1}
i番目の最後の値は
def get_min_max_pressure(n):
min_max_ps = []
for _ in range(n):
ps = list(map(int, input().split()))
min_max_ps.append([min(ps), max(ps)])
return min_max_ps
T = int(input())
for t in range(1, T + 1):
N, P = list(map(int, input().split()))
min_max_ps = get_min_max_pressure(N)
dp = [[0, 0] for _ in range(N + 1)]
l0, l1 = 0, 0
for i, min_max_p in enumerate(min_max_ps):
min_p, max_p = min_max_p
diff_min_max_p = max_p - min_p
dp[i+1][0] = min(
dp[i][0] + abs(l0 - min_p) + diff_min_max_p,
dp[i][1] + abs(l1 - min_p) + diff_min_max_p
)
dp[i+1][1] = min(
dp[i][0] + abs(l0 - max_p) + diff_min_max_p,
dp[i][1] + abs(l1 - max_p) + diff_min_max_p
)
l0 = max_p
l1 = min_p
print('Case #{}: {}'.format(t, min(dp[N][0], dp[N][1])))
Author And Source
この問題について(Codejam2022 Round1B: Controlled Inflation), 我々は、より多くの情報をここで見つけました https://zenn.dev/satojkovic/articles/87992fcbcea96e著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol