公式解説に従い、整数計画問題を導出します。

この整数計画問題は、LP緩和しても答えが高々0.5しか増えない、という性質を持ちます。

• 元の問題はb-matchingのインスタンスであるため、緩和問題は半整数性を持つ。つまり、\(x_i\)が全て整数 or 整数 + 0.5であるような最適解が存在する。
• 半整数を許容することで解を増やすことが出来るのは、\(x_i\)が全て半整数である場合のみであること、またその場合も解を\(0.5\)減らして全ての\(x_i\)を整数にすることが出来ることが示せる。(グラフにサイクルが1つしか含まれないことが重要です)

よって、LP緩和して解を求め、得られた解をfloorすれば元問題の解を得られます。

LP緩和すれば双対が取れます。これは以下のような問題になります。

\[ \begin{aligned} \mathrm{minimize} &\sum_{i=0}^{M-1} y_i C_i + \max(0, 1 - (y_i + y_{i+1})) B_i \\ s.t. & \\ & 0 \le y_i \le 1 \\ \end{aligned} \]

そして、この問題の解も半整数性を持ちます、つまり、\(y_i\)が\(0, 0.5, 1\)のいずれかであるような最適解が存在します。

よってこの問題はdp[左端の頂点の値が0 or 0.5 or 1][右端の頂点の値が0 or 0.5 or 1]という3x3行列を管理するsegment treeで解くことが出来ます。

余談ですが、N個のバケツも同様に解くことが出来ます。こちらは\(C_i\)が必ず偶数なので、LP緩和してもそもそも解が変わりません。