迷走しないようにしたい問題。
問題概要
banana at tomb but tos sound does some
のようなしりとりが与えられる。同じ文字で始まるところは 1 つにつぶすことができる。上の例で言えば
(banana at tomb but) (tos) (sound does some)
という感じでつぶすことで、長さ 3 になる。様々なつぶし方を考えたときに得られる最小長さを求めよ。
制約
- 1 ≤ N ≤ 105
- 1 ≤ ∑|wi| = 106
考えたこと
実はしりとり関係なくて、各単語の頭文字だけ見ればいいね。素直な DP でできる。
こんな感じのグラフの最短路だと思ってもよさそう。
#include <iostream> #include <string> #include <vector> using namespace std; vector<vector<int> > calcNext(const string &S) { int n = (int)S.size(); vector<vector<int> > res(n, vector<int>(26, n)); for (int i = n-2; i >= 0; --i) { for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j]; res[i][S[i+1]-'a'] = i+1; } return res; } int main() { int N; cin >> N; string S = ""; for (int i = 0; i < N; ++i) { string word; cin >> word; S += word[0]; } auto next = calcNext(S); vector<int> dp(N+1, N); dp[0] = 1; for (int i = 0; i < N; ++i) { dp[i+1] = min(dp[i+1], dp[i]+1); int ni = next[i][S[i]-'a']; if (ni >= N) continue; dp[ni] = min(dp[ni], dp[i]); } cout << dp[N-1] << endl; }