コスト \(0\) で達成できる最大スコアを考えてみます．

まず以下のような DP が考えられます．

\(dp[i][j]=P_1,\cdots,P_i\)の大小関係をうまく決めたとき，その中で \(j\) 番目に大きい値で終わる単調増加部分列の長さの最大値．

\(j\) 番目に小さい値ではないことに注意してください． こうすると DP の遷移がかなり簡単な形でかけることになります．

まず \(dp[i][j]<dp[i][j+1]\) のケースは \(dp[i][j]=dp[i][j+1]\) としてしまって良いです． また \(dp[i][j]-dp[i][j+1] \leq 1\) が元の問題の性質からわかります． よって，\(dp[i][*]\) の値を \(dp[i][j]>dp[i][j+1]\) となる \(j\) の集合で表現することができます． この集合を \(S_i\) で表すことにします． なお，便利のため \(dp[i][i+1]=0\) とし，\(S_i\) には \(i\) も含めることにします．

\(|S_i|=max(dp[i])=\) LIS 長となります． \(S_i \to S_{i+1}\) の遷移を考えると，次のような変化になるとわかります．

• \(S_i\) の中に \(A_i\) 以下の値があるなら，その中で最大の値をを消す．
• その後，\(S_i\) に \(i\) を追加する．

これを素直に set で実装すれば，コスト \(0\) のときの最大スコアは求められます．

ところで，上の \(S_i\) への操作は以下のように変形できます．

• \(S=\{1,2,\cdots,N\}\) を用意する．
• 各 \(i=1,2,\cdots,N\) について， \(S\) の中に \(A_i\) 以下の値があるなら，その中で最大の値を消す．

つまり，\(S\) に値を追加する操作を最初にすべて行ってしまって問題ありません．これは \(A_i < i\) に注意すると証明できます． また，\(i\) をループする順番を \(1,2,\cdots,N\) 以外の任意の順番にしても答えが変わらないことも証明できます．

この考察を元にコストが \(0\) 以外のケースを考えます． コストを \(1\) 支払うことで \(A_i\) を一つ選んで \(0\) にできると考えます． すると，値の大きい \(A_i\) から順に \(0\) にしていくべきだとわかります． あとはこの様子をset等でシミュレートすればよいです． コスト \(N\) の状態から初めて，値の小さい順に \(A_i\) を使った操作をすると考えると簡単に実装できます．

計算量は \(O(N \log N)\) になります．

回答例(C++)