D - String Bags

[hxrxchang]

https://atcoder.jp/contests/abc344/tasks/abc344_d

問題概要

文字列の初期値は空文字列。 文字列が複数個入っている袋がN個ある。 1 ~ N の袋の順に以下の2種類の操作いずれかをすることができる

1. 1円払って袋の中から文字列を1つ取り出す
2. 何もしない

以上の操作をして文字列Tを作る際の最小金額を求めよ。文字列Tを作れない場合もある。

解き方

1~Nまでの袋を使って、# dp[i]: Tのi文字目までをいくらで作れるか(最小金額) を求める。 計算量が N * バッグの中身 * Tの長さ の3重ループになってしまうが、制約から10 ** 6 であり問題ないことが分かればOK。

T = input()
N = int(input())

bags = []
for _ in range(N):
    inp = input().split()
    inp[0] = int(inp[0])
    bags.append(inp)

# dp[i]: Tのi文字目までをいくらで作れるか(最小金額)
dp = [float('inf')] * (len(T) + 1)
dp[0] = 0

for i in range(N):
    tmp = dp[:]
    for item in bags[i][1:]:
        for j, d in enumerate(dp):
            if d == float('inf'):
                continue
            if item == T[j:j + len(item)]:
                dp[j + len(item)] = min(tmp[j + len(item)], tmp[j] + 1)

print(dp[-1] if dp[-1] != float('inf') else -1)

https://atcoder.jp/contests/abc344/submissions/53148105