AcWing 5408. 保险箱-py
原题链接
中等
作者:
viclao
,
2024-01-14 23:52:49
,
所有人可见
,
阅读 72
# 状态机dp,f[i][0] 当前位没有产生进位 f[i][1] 当前位向前进位,f[i][2] 当前位向前借了一位
# 初始状态如果有进位或进位则需要1步操作 f[0][1] = f[0][2] = 1
# 为了方便处理进位,把x,y都反转了
f = [[float('inf')]*3 for _ in range(n + 1)]
f[0] = [0,1,1]
for i in range(1,n + 1):
a,b = int(x[i - 1]),int(y[i - 1])
# 当前位置不产生进位 = ab差值 + 上一位也没有进位或借位
f[i][0] = abs(a - b) + f[i - 1][0]
if a < 9:
# 上一位可以进位,a = 9的情况在后面处理了
f[i][0] = min(f[i][0],abs(a + 1 - b) + f[i - 1][1])
if a > 0:
# 上一位可以借,a == 0 的情况在后面处理的
f[i][0] = min(f[i][0],abs(a - 1 - b) + f[i - 1][2])
f[i][1] = 10 - a + b + f[i - 1][0] # 进位
if a == 0:
f[i][0] = min(10 - 9 + b + f[i - 1][2],f[i][0]) # 先借一个,又进一个
else:
f[i][1] = min(10 - (a - 1) + b + f[i - 1][2],f[i][1])
if a == 9:
f[i][1] = min(b + f[i - 1][1],f[i][1])
else:
f[i][1] = min(f[i][1],10 - (a + 1) + b + f[i - 1][1])
f[i][2] = a + 1 + 9 - b + f[i - 1][0] # 借一位
f[i][2] = min(f[i][2],a + 1 + 1 + 9 - b + f[i - 1][1])
if a == 0:
f[i][2] = min(f[i][2], 9 - b + f[i - 1][2])
else:
f[i][2] = min(f[i][2],a - 1 + 1 + 9 - b + f[i - 1][2])
if a == 9:
f[i][0] = min(f[i][0],f[i - 1][1] + 9 - b + 1)
print(min(f[-1]))