AOJ 2892 - Aizu Competitive Programming Camp 2018 Day 3 D しりとり圧縮 (Shiritori Compressio

問題

解法

この解法はばたこ(@btk15049)さんから聞いたものになります。

• dp[i] = i番目の単語までで、消去できる単語数の最大値

とします。
すると、i番目の単語を利用して、それより前の単語を消すかどうかの2パターンにまず分かれます。
i番目の単語を利用しない場合は、dp[i-1]になるので省略します。
i番目の単語を利用する場合、1~i-1番目の単語のなかからj番目を選んだときに、i番目とj番目の先頭の文字が同じ場合、j~i-1番目の単語が消去できます。
これはi-j個です。あとは1~j-1番目の消去数を最大にすればいいのですが、これはdp[j-1]を参照すれば求まります。
ということで、

• dp[i] = max(dp [ i -1] , dp [ j - 1 ] + i - j)

という式ができました。
ですが、このままでは間に合わないので、計算量を落とします。
文字xがi番目、j番目、k番目に存在したとします(i<j<kにします)。
このとき、iからk-1番目を消すパターンは、iからjを消すパターンにk-jを加えたものを考えることと同じです。
そして、jからk-1番目を消すパターンは、iからjを消さないパターンにk-jを加えたものになります。
ということで、iからjを消すパターンと消さないパターンのどちらの方が消去数が大きいかのみについて知っていれば、kを利用して消去するパターンの最大値を求めることができます。

• now[i][x] = i番目の文字がxのとき、消去数の最大値

とすると、一つ前の文字xがj番目であるとき、

• now[i][x] = max(dp[i-1],now[i-1][x]+i-j)

• now[i][x以外] = now[i-1][x以外]

となります。
i-jは、dp[i]について全探索しているとき、iが動くたびにインクリメントをすれば、jの位置を知らなくても求めることができます。未出現だったときの対策として、初期値を負の大きな値で行っておくといいです。
now[i][x]について、iの添え字を消去して書き直すと、

• now[x] = max(dp[i-1],now[x])

• now[x以外] = now[x以外] + 1

• dp[i] = max(dp[i-1],now[x])

になります。

提出コードはこちらになります。
コンテスト中のコードは配列外参照の可能性があったため、下から6行目のみ書き換えています。

#include <bits/stdc++.h>
using namespace std;

int now[27];
int dp[100005] = {0};
int n;
string s, dummy;

int solve();

int main() {
  int i;
  cin >> n;
  for(i = 0; i < n; ++i) {
    cin >> dummy;
    s += dummy[0];
  }
  for(i = 0; i < 26; ++i) now[i] = -1000000000;
  cout << solve() << endl;
  return 0;
}

int solve() {
  int i, j, nown;
  for(i = 0; i < n; ++i) {
    nown = s[i] - 'a';
    now[nown] = max(now[nown], dp[max(i - 1, 0)]);
    if(i != 0) dp[i] = max(dp[i - 1], now[nown]);
    for(j = 0; j < 26; ++j) ++now[j];
  }
  return n - dp[n - 1];
}