結果
問題 |
No.2147 ハノイの塔のおもちゃ
|
ユーザー |
👑 |
提出日時 | 2022-12-04 01:44:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 856 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 74,752 KB |
最終ジャッジ日時 | 2024-10-11 03:57:47 |
合計ジャッジ時間 | 1,384 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 |
ソースコード
MOD = 10 ** 9 + 7 n = int(input()) C = [0] for _ in range(n): C.append(C[-1] * 2 + 1) S = input().rstrip("A") if not S: print(0) exit() if len(S) == 1: print(1) exit() dp = [1] * 3 s = "ABC".index(S[0]) dp[s] = 0 for x, s in enumerate(S[1:], 1): s = "ABC".index(s) ndp = [float("inf")] * 3 for i in range(3): for j in range(3): if j == s: if i == j: ndp[i] = min(ndp[i], dp[j]) else: ndp[i] = min(ndp[i], dp[j] + C[x + 1]) else: if i == j: ndp[i] = min(ndp[i], dp[j] + 2 * C[x] + 1) elif i == s: ndp[i] = min(ndp[i], dp[j] + C[x]) else: ndp[i] = min(ndp[i], dp[j] + C[x] + 1) dp = ndp print(dp[0] % MOD)