## F - Brave CHAIN 解説 by evima

(Editorial: ynymxiaolongbao)

Among the five cards that is arranged in the \(i\)-th operation, the numbers on the rightmost \(3\) cards are \(A[3i]\), \(A[3i+1]\) and \(A[3i+2]\), which is independent of the operations before the \(i\)-th one. On the other hand, the pair of numbers on the leftmost \(2\) cards is dependent on the operations before the \(i\)-th one.

We use Dynamic Programming (DP).

Let \(DP[i][x][y]\) be the maximum score after the \(i\)-th operation where the leftmost number is \(x\) and the second leftmost number is \(y\).

We assume that, if the third, fourth and fifth number from the left are the same, we always remove those three cards. One can prove by contradiction that this does not lose the optimality. In such case, we can add \(1\) to the answer and regard those \(3\) card as being disappeared.

Among the third, fourth and fifth numbers, if two of them are the same, let \(p\) be the common number, \(q\) the other, and \(k\) be any integer between \(1\) and \(N\) (inclusive), then maximize \(DP[i+1][k][q]\) by \(DP[i][p][k]+1\) or \(DP[i][k][p]+1\) and so on. The time complexity is \(O(N)\).

Among the third, fourth and fifth numbers, let \(p\) be one of them and \(q\) and \(r\) be the other, then maximize \(DP[i+1][q][r]\) by \(DP[i][p][p] + 1\). The time complexity is \(O(1)\).

Let \(p\), \(q\) and \(r\) be the third, fourth and fifth numbers respectively, and \(k\) and \(l\) be any integer between \(1\) and \(N\) (inclusive), then maximize \(DP[i+1][p][q]\), \(DP[i+1][p][r]\) or \(DP[i+1][q][r]\) and others with the maximum value of \(DP[i][k][l]\). This can be processed in an \(O(1)\) time if the maximum value of \(DP[k][l]\) is managed.

Among the third, fourth and fifth numbers, let \(p\) be one of them, and \(k\) and \(l\) be any integer between \(1\) and \(N\) (inclusive), then maximize \(DP[i+1][k][p]\) with the maximum value of \(DP[i][k][l]\) (where only \(l\) is a variable), and maximize \(DP[i+1][l][p]\) by the maximum value of \(DP[i][k][l]\) (where only \(k\) is a variable). If the values above are managed, they can be processed in \(O(N)\) time.

Let \(k\) and \(l\) be any integer between \(1\) and \(N\) (inclusive), then maximize \(DP[i+1][k][l]\) by \(DP[i][k][l]\). However, if you reuse the array and use \(DP[i][k][l]\) as the initial value of \(DP[i+1][k][l]\), you do not need to do this process.

The maximum value can be processed in an \(O(1)\) time each, since the value of DP never decreases.

The time complexity for each \(i\) is \(O(N)\), so the overall time complexity is \(O(N^2)\).

投稿日時:

最終更新: