DP シリーズ。
問題#
問題を見ると、Luogu
隣接する同じ数字を結合して、数字を 1 つ増やします。得られる最大値を求めます。
考察#
最初に思いついたのは基本的な区間 DP ですが、説明は省略します：
long long ans = 0;
for(int len = 2; len<=N; len++){
for(int i = 1; i+len-1<=N; i++){
int y = i+len-1;
for(int k = i; k<y; k++){
if(DP[i][k] == DP[k+1][y]){
DP[i][y] = max(DP[i][y], DP[i][k] + 1);
}
}
ans = max(ans, DP[i][y]);
}
}
cout << ans << endl;
しかし、$ 2 \leq n \leq 262144 $ なので、明らかに MLE になります。
最適化#
アイデアを借りて、倍増のような方法を使うことができることに気づきました。
状態 f[i][j] は、合成後の結果が i で右端点が j の区間の左端点の位置を表します。値が 0 の場合は不可能です。
なぜなら、問題は隣接する 2 つの同じ区間を見つけて結合することです。つまり：
f[i][j] = f[i-1][f[i-1][j]];
f[i][j] を i-1 に合成できる2つの区間に分割する
つまり
f[i-1][j]
|------<i-1>-----|----<i-1>-----|
j f[i-1][f[i-1][j]]
もし f[i-1][j] または f[i-1][f[i-1][j]] が成立しない場合、f[i][j] も成立しないので、0 に遷移します
では、結果をどのように表現しますか？
ans を記録し、f[i][j] が可能な場合は ans を更新します。i が増加するので、max 演算は必要ありません。
次のようになります
for(int i =2; i<=58; i++){
for(int j = 1; j<=N; j++){
if(!DP[i][j]){
DP[i][j] = DP[i-1][DP[i-1][j]];
}
if(DP[i][j]){
ans = i;
}
}
}
注意点として、倍増結合を行うため、$log_2 {262144} + 40 = 58$ が可能な最大値です。
初期化#
明らかに結合しない場合も可能なので、入力時に初期化します
for(int i = 1; i<=N; i++){
int in;
cin >> in;
DP[in][i] = i+1;
}
i+1 について：区間の重複を避けるため、f[i][j] は左閉右開区間を表すため、右端点は i+1 です。
まとめ#
この問題は区間 DP の状態の最適化です。DP の学習の道は長く、練習が必要です。