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