けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2892 しりとり圧縮 (AUPC 2018 day3 D)

迷走しないようにしたい問題。

問題へのリンク

問題概要

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;
}