F - Brave CHAIN Editorial by ynymxiaolongbao
(解説:ynymxiaolongbao)
\(i\) 回目の操作で並べ替える \(5\) 枚のうち、右の \(3\) 枚に書かれた数字は \(A[3i]\) , \(A[3i+1]\) , \(A[3i+2]\) であり、\(i\) 回目以前の操作に関わらず決まった値になります。逆に、左の \(2\) 枚に書かれた数字の組は \(i\) 回目以前の操作によって変わる可能性があります。
動的計画法を用います。
\(DP[i][x][y]\) を \(i\) 回目の操作の後、一番左の数字が \(x\) で、二番目に左の数字が \(y\) であるときの、\(i\) 回目までの操作で得た総得点の最大値とします。
\(i\) 回目の操作の後左から \(3,4,5\) 番目の数字が等しいときは、必ずそれら \(3\) 枚を取り除くことにします。これで最適性が損なわれないことは背理法によって証明できます。このとき、答えに \(1\) を加算し、それら \(3\) 枚が無かったかのように計算を続行すれば良いです。
\(3,4,5\) 番目の数字に等しい数字のペアがあるとき、その値を \(p\)、残りの一つの値を \(q\) 、\(k\) を \(1\) 以上 \(N\) 以下の任意の整数として、\(DP[i+1][k][q]\) を \(DP[i][p][k]+1\) や \(DP[i][k][p]+1\) で最大化します。計算量は \(O(N)\) です。
\(3,4,5\) 番目の数字の一つを \(p\)、残りを左から \(q,r\) として、\(DP[i+1][q][r]\) を \(DP[i][p][p]+1\) で最大化します。計算量は \(O(1)\) です。
\(3,4,5\) 番目の数字を左から \(p,q,r\) 、\(k,l\) を \(1\) 以上 \(N\) 以下の任意の整数として、\(DP[i+1][p][q]\) や \(DP[i+1][p][r]\) や \(DP[i+1][q][r]\) を \(DP[i][k][l]\) の最大値で最大化します。\(DP[i][k][l]\) の最大値を管理していれば \(O(1)\) で処理できます。
\(3,4,5\) 番目の数字の一つを \(p\)、\(k,l\) を \(1\) 以上 \(N\) 以下の任意の整数として、\(DP[i+1][k][p]\) を \(DP[i][k][l]\) (\(l\) のみ変数)の最大値、 \(DP[i+1][l][p]\) を \(DP[i][k][l]\) (\(k\) のみ変数)の最大値で最大化します。前述の最大値をそれぞれ管理していれば \(O(N)\) で処理できます。
\(k,l\) を \(1\) 以上 \(N\) 以下の任意の整数として、\(DP[i+1][k][l]\) を \(DP[i][k][l]\) で最大化します。しかし、配列を使い回し、\(DP[i][k][l]\) を \(DP[i+1][k][l]\) の初期値とすれば、この処理は必要なくなります。
最大値の管理については、\(DP\) の値が減少しないことに注意すれば更新ごとに \(O(1)\) で処理できます。
各 \(i\) での処理にかかる計算量が \(O(N)\) となり、計算量は全体で \(O(N^2)\) になります。
posted:
last update: