BOJ 14226表情

10909 ワード
2021.05.14 テキストリンク
https://www.acmicpc.net/problem/14226
2秒、512 MBメモリ
input :
  • S (2 ≤ S ≤ 1000)
    • output :
    出力
  • Sに要する時間の最大値は
    • である.
    条件:
  • は、以下の3つの演算のみを用いるS個の表情記号
    • を生成する.
  • 画面のすべての表情をクリップボードにコピーして保存します.
  • クリップボードのすべての表情を画面に貼り付けます.
  • 画面の1つの表情記号を削除します.
  • すべての演算には1秒かかります.
    • 最初のインデックスの値は0です.最初の表情が1の文字列を与えるからです.
    コピー、貼り付け削除だけを実施すればいいと思っていたので聞いてみました.
    この場合,2の二乗以外は実現不可能である.
    二重複文を使用してもbfsを使用しても.
    繰り返し文を用いた場合,2倍の貼り付け演算を実現するためには,現在の数字がiの倍数であると判断する必要がある.そこで1秒の追加削除演算を実現します.
    for i in range(1, 1000):
    for j in range(i+1, 1001):
        if j == i*2:
            emo[j] = min(emo[i]+2, emo[j])
        elif j%i == 0:
            emo[j] = min(emo[i]+j//i, emo[j])
        
        if emo[j-1] > emo[j]+1:
            emo[j-1] = emo[j]+1
    上記の方法またはbfsを使用して、すべての演算を最初に実行すると、値を更新してキューに入れて実行を続行できます.2 D配列を使用して実行されるため、この値に何があるかを決定し、範囲に注意する必要があります.
    import sys
from collections import deque

s = int(sys.stdin.readline())
ans = [[-1] * (s + 1) for i in range(s + 1)]
ans[1][0] = 0

q = deque([(1, 0)])

while q:
    x, y = q.popleft()

    if ans[x][x] == -1:
        ans[x][x] = ans[x][y] + 1
        q.append((x, x))

    if x + y <= s and ans[x + y][y] == -1:
        ans[x + y][y] = ans[x][y] + 1
        q.append((x + y, y))

    if x - 1 >= 0 and ans[x - 1][y] == -1:
        ans[x - 1][y] = ans[x][y] + 1
        q.append((x - 1, y))

ret = float('INF')
for item in ans[s]:
    if item != -1 and ret > item:
        ret = item
print(ret)
    Dijkstra's algorithms(find the shortest path)
    [Sparta]21.09.14開発ログ8