まず、\(d[i][p][q]\) を「\(k=i\) 番目の操作まで終わった時点で \(x=p,y=q\) となっている時の \(c\) の値の最大値」と定義した DP を考えます。この DP は空間計算量が \(O(N^3)\) であり、メモリ制限・実行時間制限に間に合わないのでこの DP を改善することを考えます。

まず、各 \(k\) に対し \(\max(x,y)=\max(P_1,P_2,\ldots,P_k)\) が成り立ちます。したがって、上の動的計画法から \(1\) つパラメータを削除することができ、\(d[i][p]\) を「\(k=i\) 番目の操作まで終わった時点で \(\min(x,y)=p\) となっている時の \(c\) の値の最大値(ただし \(\min(x,y)=p\) とする操作が存在しない場合は \(-\infty\))」とした DP が回ります。

この DP の遷移を考えます。

① \(P_i < \max(P_1,P_2,\ldots,P_{i-1})\) のとき

\(\displaystyle d[i][P_i]=\max_{0\le j < P_i}d[i-1][j]+1\) です。また、\(p\neq P_i\) なら \(d[i][p]=d[i-1][p]\) です。

② \(P_i > \max(P_1,P_2,\ldots,P_{i-1})\) のとき

\(x,y\) どちらかの値は必ず \(P_i\) になります。\(\min(x,y)\) の値は小さい方が良いので、必ず大きい方を選び \(P_i\) にするとして良いです。このことから \(d[i][p]=d[i-1][p]+1\) となります。

以上の遷移はセグメント木に乗せることで in-place に行うことができます。計算量は \(O(N\log N)\) です。

さらに、もう少し考察を進めることで答えは「\(P\) から \(P_i>\max(P_1,P_2,\ldots, P_{i-1})\) を満たす要素を取り除いた整数列を \(Q\) とした時の、取り除いた要素数と \(Q\) の LIS の長さの和」となることが分かります。この事実を用いて LIS を求めても正答となります。

実装例(Python3)

import sys
from atcoder.segtree import SegTree

input = sys.stdin.readline
INF = 10**9
n = int(input())
a = list(map(int, input().split()))
seg = SegTree(max, -INF, n + 1)
seg.set(0, 0)
ma = 0
ans = 0
for v in a:
    if ma < v:
        ans += 1
        ma = v
    else:
        seg.set(v, seg.prod(0, v) + 1)
print(ans + seg.all_prod())

実装例(Python3)

import bisect


def lis(seq):
    if len(seq) == 0:
        return 0
    LIS = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    return len(LIS)


n = int(input())
p = list(map(int, input().split()))
q = []
ans = 0
max_val = -1
for v in p:
    if max_val < v:
        max_val = v
        ans += 1
    else:
        q.append(v)
print(ans + lis(q))