本解同様に二分木を作り、各頂点 \(i\) について \(\mathrm{dp}_{i,j}\) を「\(i\) を根とする部分木に属する \(l_k\) の最大値が \(j\) 以下の時のコストの最小値」とします。すると、これは \(i\) を根とする部分木の頂点数 \(+1\) 個の区間に対応する一次関数として表せ、(部分木のサイズに偏りが無いことを考えると) \(\mathrm{O}(N^2 2^N)\) や \(\mathrm{O}(N2^N)\) で求められます。