問題
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
解法
01で解くのをNK回すれば良いです。
K = 1のときの最適化問題に戻ってdpを考えると、
状態A : 1のときにコスト1かかり、0のときにコスト0かかる。
状態B : 0のときにコスト1かかり、1のときにコスト0かかる。この状態にするときにコストCかかる。
をうまく行き来するのが最適なので、
dp[i][f] = i 要素見て今の状態が f のときの最小コスト、というdpで解けます。
状態Bは操作2で区間+1をしたあとに操作1で1点-1をするのに対応しています。
dp[i][0]の値とdp[i][1]の値をキーにすることで(Nより大きくなったらNとして良い)最小コストが0,1,...になる数列の数を数えられます。
計算量はO(NK(NK+N^3)) です。
提出
