\(f(A,T)\) を、できる限り数え上げにしやすいように求めます。

まず、\(x\) は先頭から貪欲に決めてよいです。

（証明）\(x_i\) を決めるとき、それより前の値によらず選べる値が存在することを示せばよいです。

\(c_j\) を、\(x_i\) を \(j\) にしたときに \(y_i\) の値とします。このとき、以下の条件が成り立ちます。

• \(0\leq c_0\leq c_1\leq \dots\leq c_{i-1}\leq i-1\)

\(c_j=j\) なるindexが存在しないと仮定すると、先頭から帰納的に \(j\lt a_j\) がわかりますが、これは \(c_{i-1}\leq i-1\) と矛盾します。よって \(a_j=j\) なるindexは必ず存在し、そのindexは \(x_i\) として適します。（証明終わり）

\(x_i\) の決め方を考えます。

数列 \(z\) を、\((A_1+T\times x_1,A_2+T\times x_2,\dots,A_{i-1}+T\times x_{i-1})\) を昇順に並べたものとします。すると、

• \(z_{i-1}-T\times (i-1)\lt A_i\) なら \(x_i=i-1\) に、
• そうでなく、\(z_{i-2}-T\times (i-2)\lt A_i\) なら \(x_i=i-2\) に、
• …
• そうでなく、\(z_1-T\times 1\lt A_i\) なら \(x_i=1\) に、
• そうでなければ \(x_i=0\) に

すればよいです。

\(\displaystyle Z_j=\min_{j\leq k} z_k-T\times k\) とした数列 \(Z\) を考えて、\(A_i\) を処理したときに \(Z\) がどうなるか考えます。

• \(Z\) のソート順を崩さないところに \(A_i\) を挿入する（同じ数ならその先頭）。
• 挿入したindexを \(j\) とすると、\(x_i=j-1\) となる。
• \(Z_j,Z_{j+1},\dots,Z_i\) から \(T\) を減算する。
• \(Z_1,Z_2,\dots,Z_{j-1}\) に \(Z_j\) を \(\text{chmin}\) する。

もとの \(Z\) の要素の気持ちになると、その要素と \(A_i\) の大小によってのみ、次の値が決まることがわかります。\(x_i\) は \(Z\) のうち \(A_i\) より小さい要素の個数になることも踏まえると、\(Z\) に含まれる値の度数分布をDPすればよいです。

\(Z\) に含まれうる値は \(O(N^2K)\) 個なので、計算量は \(O(N^3K^2)\) です。