しりとり圧縮 (Shiritori Compression) [Aizu Competitive Programming Camp 2018 Day 3 D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/D

前提知識

• 動的計画法

考察過程

1. 難しく見えるし、最小値を求めているし、DAGっぽくもあるので、DP方針で考える
2. 「dp[i] := i番目まで到達するための単語の最小個数」がぱっと思いつくDP
3. dp[i]を確定したいが、遷移元はdp[i-1]とi番目の先頭がcであれば、i番目より前のcの1つ前のdp[j]
4. 文字ごとにdp[j]の最小値を持っておけば遷移を高速化できる
5. 解けた

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149880

DPで解く。
dp[i] := 最後がi番目の単語になるために必要な最小単語数
i番目の単語の頭文字をcとすると、i番目より前で次の単語の頭文字がcである
dp[j]からコスト1で遷移することが分かる。
1つ前の単語からの遷移もこれに含まれるので、分けて処理を書く必要はない。
すべてチェックするとO(N^2)でTLEなので、累積和っぽくメモ化しておこう。
opt[c] := 次の単語がcである単語のdp[j]の最小値
これを更新しながらやればO(1)で更新できるので間に合う。

int N;
string W[101010];
int dp[101010], opt[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> W[i];

    rep(i, 0, N + 1) dp[i] = inf;
    dp[0] = 0;
    rep(i, 0, 26) opt[i] = inf;

    rep(i, 1, N + 1) {
        int c = W[i - 1].front() - 'a';
        chmin(opt[c], dp[i - 1]);
        
        dp[i] = opt[c] + 1;
    }

    cout << dp[N] << endl;
}