D - Shift vs. CapsLock

[hxrxchang]

https://atcoder.jp/contests/abc303/tasks/abc303_d

問題概要

a, shift, caps lock しかないキーボードがある。

• a を押すと caps lockがOFFなら a, ONなら A が出力される。この操作にXミリ秒かかる。
• Shift と A を同時に押すと、caps lockがOFFなら A、ONなら a が出力される。この操作にYミリ秒かかる。
• caps lockを押すとその状態がトグルされる。この操作にZ秒かかる。

最初はcaps lockがOFFである。文字列Sを出力するのに何ミリ秒かかるか求めよ。

解き方

S[i]までを入力した時に、dp[0]: caps lockがOFFであるときの最小時間, dp[1]: caps lockがONであるときの最小時間 を求める。

X, Y, Z = map(int, input().split())
T = input()

# T[:i]までを作って、dp[0]: CapsロックがOFF, dp[1]: CapsロックがON であるときの最小のコスト
dp = [float('inf')] * 2
dp[0] = 0
dp[1] = Z

for i in range(1, len(T) + 1):
    tmp = dp[:]
    target = T[i - 1]
    if target == 'a':
        dp[0] = min(tmp[0] + X, tmp[1] + Z + X, tmp[1] + Z + Y)
        dp[1] = min(tmp[0] + X + Z, tmp[0] + Z + Y, tmp[1] + Y)
    else:
        dp[0] = min(tmp[1] + X + Z, tmp[1] + Z + Y, tmp[0] + Y)
        dp[1] = min(tmp[1] + X, tmp[0] + Z + X, tmp[0] + Z + Y)

print(min(dp))

https://atcoder.jp/contests/abc303/submissions/53221298