TopCoder SRM 490 Div1 Medium QuickT9

問題

次のような携帯の文字列入力がある。

2-9のボタンに次の文字が対応している。
2 a,b,c
3 d,e,f
4 g,h,i
5 j,k,l
6 m,n,o
7 p,q,r,s
8 t,u,v
9 w,x,y,z

携帯は次の三つの内部状態を持つ。
D: 今まで入力した数字
U: 未確定の文字列
F: 確定の文字列

辞書が与えられて、次のようにD, U, Fが決まる。
最初D, U, Fは空である。

2-9のボタンを押す：　Dの末尾にその数字が加わる。validでない場合、なかったことにされる。
右ボタンを押す：　Fの末尾にUが加わる。D, Uは空に戻る。
Cボタンを押す：　Fの末尾にUが加わる。D, Uは空に戻る。Fが空でない場合、Fの末尾1文字を削除する。
*ボタンを押す：　Uが現在のDに対してvalidな文字列のうち、辞書順で次に最小な文字列に変わる。

validとは文字列が辞書のどれかの単語の、Dの桁数分の文字を、対応するボタンの数字にしたときに、それがDに一致しているような状態をいう。

このとき、与えられた文字列wordを入力するために必要なボタン押下の回数の最小値を求めよ。
入力が不可能な場合は-1を返せ。

制約条件

辞書の単語は2500個以下くらい。
辞書の単語の長さの総和は2500以下くらい。
wordの長さは50以下

方針

入力可能な文字列に対して、その文字列を入力するのに何回ボタンを押さなければならないかを最初に求める。
そしたら、それを使ってwordが何回で作れるかをDPする。

文字列を入力するのに何回ボタンを押さなければならないかであるが、
まず入力できる文字は、辞書の単語のprefixのみ。
prefixが一つ決まると、それを入力するためのDが決まるので、
Dごとにsetを持っておけば、同じDの中で何番目かが簡単に求まる。

ソースコード

int key[256], dp[51];

class QuickT9 {
	public:
	int minimumPressings(vector <string> t9, string word) 
	{
		int a[] ={3, 3, 3, 3, 3, 4, 3, 4}, b = 0;
		rep(i, 8) rep(j, a[i]){
			key['a' + b++] = i;
		}
		rep(i, 51) dp[i] = inf;
		
		vs v;
		rep(i, t9.size()){
			stringstream ss(t9[i]);
			string s;
			while(ss >> s) v.pb(s);
		}
		
		int n = v.size(), m = word.size();
		sort(all(v));
		
		map<string, set<string> > M;
		map<string, int> N;
		rep(i, n){
			string k;
			rep(j, v[i].size()){
				k += key[v[i][j]] + '0';
				M[k].insert(v[i].substr(0, j + 1));
			}
		}
		
		fr(i, M){
			int k = 0, c = i->first.size();
			fr(j, i->second){
				if(!N.count(*j) || N[*j] > c + k + 1) N[*j] = c + k + 1;
				string s;
				for(int l = 1; l < j->size(); l++){
					s += (*j)[l - 1];
					if(!N.count(s) || N[s] > c + k + j->size() - l) N[s] = c + k + j->size() - l;
				}
				k++;
			}
		}
		dp[0] = 0;
		rep(i, word.size()){
			for(int j = 1; j + i <= m; j++)
			if(N.count(word.substr(i, j)))
			dp[i + j] = min(dp[i + j], dp[i] + N[word.substr(i, j)]);
		}
		return dp[m] == inf ? -1 : dp[m];
	}
};