解説

全てのキーボードで全てのワードの打ち方を検証する、 $O(N^Q)$ 解法では間に合いません。 そこで、 $i$ 番目のワードを入力する際、 $i-2$ 番目以前に使用したキーボードの情報は不要である事に注目します。すると、以下のような動的計画法が考えられます。

• $dp[i][j]$ ＝ $i$ 番目のワードを $j$ 番目のキーボードで入力する場合の、 $i$ 番目までのコストの総和の最小値

状態数は、各ワード毎に使用するキーボードが存在するため、 $O(NQ)$ です。

各遷移について、 $i$ 番目のワードを$j$番目のキーボードで入力するコストを計算してから実施する事で、 $i-1$ 番目に使用したキーボードを全探索する $O(N)$ で計算する事ができます。

全体として $O(N^2Q)$ で計算する事ができます。

C++での実装例は以下の通りです。

　
　

より高速な解法

各遷移について、 $i-1$ 番目に使用したキーボードを全探索する必要はなく、以下の $2$ 通りについて調べれば十分です。

• $i-1$ 番目のワードと同じキーボードを使用する場合
• $i-1$ 番目までの最小コストが最も小さいキーボードを使用する場合

このように計算する事で、各遷移を $O(1)$ で求め、全体として $O(NQ)$ に高速化する事が出来ます。

C++での実装例は以下の通りです。