AUPC 2018 day3 D: Shiritori Compression

問題

しりとりになっている英単語の列wiが与えられる。この列には次のような操作を好きなだけ行うことができる。
i＜jなるi, jについてwiとwjの先頭の文字が等しいとき、列からwi, wi+1, ..., wj-1を取り除く。
最小でいくつまで要素を減らせるか。

制約

単語の個数≦10^5

方針

n+1頂点からなるグラフvを考える。
i＜jなるi, jについてwiとwjの先頭の文字が等しいときvj+1からwiに辺を張る。
単語wiを使うということを、vi+1から出る辺を通るということとすると、操作後に残った列は、グラフ上で頂点vnから頂点v0へ移動するパスに対応することになる。

したがってこのグラフ上で、頂点vnから頂点v0への最短路の長さを求めればいい。
このグラフはDAGであり（番号が小さい頂点にしか辺がないため）、先頭の文字が等しいところは全部辺があるので、ダイクストラ等をせずに先頭の文字ごとに今までの最短距離をもっておけば十分。

ソースコード

int main() {
	cin.tie(0); cin.sync_with_stdio(0);
	int n; cin >> n;
	vector<string> w(n);
	rep(i, n) cin >> w[i];
	vector<int> dp(26, (int)1e9);
	int prev = 0;
	for(int i = n - 1; i >= 0; i--){
		int k = w[i][0] - 'a';
		dp[k] = min(dp[k], prev + 1);
		prev = dp[k];
	}
	cout << prev << endl;

	return 0;
}