SRM370 Div2 1000
問題
T9と呼ばれる文字入力方式で、文字を入力する。
これは、アルファベットを入力するのに、
a,b,c->2
d,e,f->3
g,h,i->4
j,k,l->5
m,n,o->6
p,q,r,s->7
t,u,v->8
w,x,y,z->9
のように電話のキーパッドの数字1つで表す。このほかに「辞書の次」「新しい文字」「スペース」のボタンを押すことができる。
たとえば、辞書に{"bad","apple"}とある場合、ボタン2を押すと(badの1文字目の)"b"と表示される。「辞書の次」ボタンを押すと2はa,b,cが割り当たっているので、(appleの1文字目の)"a"が表示される。続けてボタン2を押すと、「2,2」と入力したことになるので、badのbaが対応して、"ba"と表示される。
新しい文字を始める時は、スペースボタンを押してスペースを入れるか、新しい文字ボタンを押せば、そこから新しい文字を入力できる。T9は、新しい文字を始めた際には、辞書の最初から検索しなおす。
辞書となる文字列と、入力したい文字列が与えられる。その入力したい文字列を入力するのに必要な最小となる押す回数を返す。もし辞書を使って入力できない場合は-1を返す。
考え方
dp。
流れは、「辞書文字列を単語に分解」→「辞書の単語の部分文字列について、それを入力するための最小押し回数を求める」→「入力したい文字列についてdpで最小押し回数を求める」。
■「辞書文字列を単語に分解」
文字列を1つにまとめてstringstreamなどで単語文字列にわけるだけ。
■「辞書の単語の部分文字列について、それを入力する為の最小押し回数を求める」
キーパッドで文字列keyの順で入力された場合("23532"など)、その順番にマッチする辞書の単語の部分文字列をすべて見つけ、vector配列にいれる。
1つ以上見つかった場合は、そのvector配列[i]は、そのkey入力(keyの長さ)+i回「辞書の次」ボタンを押した場合に相当するので、map
■「入力したい文字列についてdpで最小押し回数を求める」
入力したい文字列msgについて、msgで連続する文字列を入力するために必要な最小押し回数を求める。これは、その文字列のj文字目から新しい文字列として入力する場合を考えて、
dp[i] = min(dp[i], dp[j]+{jからiまでの部分文字列を入力するに必要な最小押し数}+「新しい文字」ボタンを押すかどうか)で求められるので、iとjの2重ループを回す。
すべての連続する文字列について、その最小押し数を合計し、スペースの個数を足したものが答えになる。
