以下の二つの情報を持って \(S\) の要素数の小さい順にDPすることで、詳細は省きますが遷移が \(O(1)\) となります。

• \(DP1[S][last]=S\) に含まれる要素までをすでに確定させていて、最後の要素を \(last\) で使うときのコストの最小値
• \(DP2[S]=S\) に含まれる要素までをすでに確定させているときのコストの最小値(最後の要素は関係なし)

そのため、時間計算量は \(O(N2^N)\) なので、これは十分間に合います。

ただし、 \(DP1\) のメモリ確保を愚直にやると空間計算量も \(O(N2^N)\) となってしまい、MLEとなってしまいます。

これの対処法としては、 DPの遷移には \(S\) の要素数がひとつだけ少ないものしか必要ないことを利用して、\(2\times\text{C}(22,11) \times 22\) の配列を確保することでMLEをかろうじて回避することができます。

MLE実装例(C++23,951MB)

AC実装例 (C++23,401MB)