解法
まず, t9 の各文字列の k 文字目までを作るのにかかるコストを計算します。
これには, t9 の各文字列 s について, s の k 文字目以下の番号(問題文の D というやつ) が一致しているやつを列挙し, それらの中で s.substr(0, k) が何番目に来るのかを求めれば良いです。
これにより, t9 から作ることの出来る文字列について, それを作るために必要な最小操作回数が得られます。
最小操作回数が得られたら, 後はダイクストラします。
d[i] = (i 文字目までを構成するのにかかる操作回数) として, グラフは以下のように構成できます。
i 文字目から何らかの文字列 p を付け加えた後, C を何回か行うことにより, 新しい文字列を作ることを考える。
word[i]+p という文字列から, 後ろの文字を削っていって, word.substr(0, j) と一致したら, 頂点 i から 頂点 j へ辺を追加します。
このような遷移が t9 を使ってできる遷移の全てなので, このグラフについてダイクストラすれば答えが得られます。
struct edge { int v; ll w; edge() {} edge(int v, ll w) : v(v), w(w) {}; }; vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } int number(char c) { if ('a' <= c && c <= 'c') return 2; if (c <= 'f') return 3; if (c <= 'i') return 4; if (c <= 'l') return 5; if (c <= 'o') return 6; if (c <= 's') return 7; if (c <= 'v') return 8; return 9; } vector<string> candString(const string s, const vector<string>& cand) { vector<string> ret; int len = s.size(); for (string t : cand) { if (t.size() < s.size()) continue; string u = t.substr(0, s.size()); bool ng = false; for (int i = 0; i < len; i++) { if (number(s[i]) != number(u[i])) { ng = true; break; } } if (!ng) ret.push_back(u); } sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } class QuickT9 { public: int minimumPressings(vector <string> t9, string word) { vector<string> cand; for (string s : t9) { stringstream ss(s); string t; while (ss >> t) cand.push_back(t); } map<string, int> mp; for (string s : cand) { int len = s.size(); for (int k = 1; k <= len; k++) { string t = s.substr(0, k); vector<string> cands = candString(t, cand); int plus = 0; for (; ; plus++) if (cands[plus] == t) break; if (mp.find(t) == mp.end()) mp[t] = k+plus+1; else mp[t] = min(mp[t], k+plus+1); t = s.substr(0, k-1); if (mp.find(t) == mp.end()) mp[t] = k+plus+1; else mp[t] = min(mp[t], k+plus+1); } } // dijkstra int n = word.size(); vector<vector<edge> > G(n+1); for (int i = 0; i < n; i++) { for (auto p : mp) { string s = word.substr(0, i) + p.first; int cost = p.second; while ((int)s.size() > i) { if (s == word.substr(0, s.size())) G[i].emplace_back(s.size(), cost); cost++; s.pop_back(); } } } auto d = dijkstra(n+1, G, 0); ll ans = d[n]; if (ans > 100000000) ans = -1; return (int)ans; } };