atcoder.jp
問題
- 最初に文字列$T$と、空文字列$S$を持ってるよ
- 文字列がいくつか入った袋が$N$個あるよ
- 以下の手順を$i=1,2,...,N$について繰り返すよ
- 1円を払って、袋$i$から好きな文字列を1つ選んで、文字列$S$の末尾に連結する
- 何もしない
- 最終的に文字列$S$と文字列$T$が一致する？
成約
- $1 \leq |T| \leq 100$
- $1 \leq N \leq 100$
- $1 \leq A_{i} \leq 100$
- $1 \leq S_{i,j} \leq 10$
思考
- 雰囲気から、DP！
- 初期値：「空文字列」を作るための最小コスト＝0
- 遷移：
- 「今作れてる文字列」に、新しい袋から文字列を1つ取り出して、引っ付けてみる
- もしTの先頭と一致しているなら、とりあえず採用！
- 丁寧にindex（何文字目まで作成できた！）で見ていったほうが良いんだろうなぁ、と思ってはいる…
- が、
T.startswith()で接頭語だけに絞れば、割と余裕で通ったので良かった
- 文字列の長さがどれも短かったから…？
- 正直、Tが$10^{6}$みたいな長さしてたらTLE頂いてた可能性は十分有り
- そのうちindexでちゃんと書き換える :TODO
コード
T = input()
N = int(input())
words = []
for i in range(N):
tmp = input().split()
words.append(tmp[1:])
now_s = set()
now_s.add("")
cost_d = dict()
cost_d[""] = 0
for i in range(N):
next_s = set()
for now_word in now_s:
next_s.add(now_word)
for add_word in words[i]:
tmp = now_word + add_word
if T.startswith(tmp):
next_s.add(tmp)
if tmp in cost_d.keys():
cost_d[tmp] = min(cost_d[tmp], cost_d[now_word] + 1)
else:
cost_d[tmp] = cost_d[now_word] + 1
now_s = next_s
print(cost_d[T] if T in cost_d.keys() else -1)
