\(A\) の値をすべて \(1\) ずつ減らしてみます．

\(0,1,\cdots,N\) の \(N+1\) 点からなるグラフを考え，\(A_i \geq 0\) なる \(i\) については \(i \to A_i\) に辺を貼ることにします．

すると，よい数列は，\(N+1\) 個の頂点をいくつかのパスに分解することに対応します．

\(A\) の長さ \(K\) の単調減少部分列は，\(K\) 重にネストされた辺の集合と見ることができます． つまり，頂点の組 \(L_1<L_2<\cdots<L_K<R_K<\cdots<R_1\) であって，\(R_i \to L_i\) と辺が貼られているような組です．

このような \(K\) 本の辺を \((0,1,\cdots,N)\) のパス分解に埋め込む方法の場合の数を数えていきます． 今注目している \(K\) 本の辺を含む \(K\) 個のパスと，それ以外の頂点に分けて考えることにします． \(K\) 個のパスのいずれかに含まれる頂点を，更に左右で二つに分けて考えます． \(L_K\) およびその左にある頂点の集合を \(A\)，それより右にある頂点の集合を \(B\) と置きます． \(A\) および \(B\) は，それらだけを見た時，\(K\) 本のパスに分解されているはずです． また逆に，\(A\) と \(B\) のパス分解を決めてしまえば，その間を結ぶ \(K\) 本の辺は一意に定まります．（\(A\) の中で右から \(i\) 番目にあるパスの始端と，\(B\) の中で左から \(i\) 番目にあるパスの終端が対応する．）

結局，\(A\) のサイズと \(B\) のサイズを決め打ってしまえば，以下の値をすべてかけることでそれに対応するような \(K\) 本の辺のとり方を数え上げられることになります．

• \(N+1\) 頂点のうち，\(A,B\) に含まれる点はどれか．
• \(A\) を \(K\) 本のパスに分解する場合の数
• \(B\) を \(K\) 本のパスに分解する場合の数
• \(A,B\) 以外の頂点のパス分解の総数

パス分解の総数は，\(dp[i][j]=i\) 頂点のグラフを \(j\) 本のパスに分解する場合の数，と定めることで，必要なすべての値を \(O(N^2)\) で求めることができます．

計算量は全体で \(O(N^2)\) になります．

解答例(c++)