綺麗さ、おいしさ、人気度を「カテゴリ」と呼び、それぞれカテゴリ 1, 2, 3 と言います。

ケーキが \(\max(X_{i}, Y_{i}, Z_{i})\) の大きい順に並んでいると仮定したとき、以下が成り立ちます。

• ケーキ \(1\) からケーキ \(2K\) のうち、採用されないケーキの数が \(2\) 個以下であるような最適解が存在する。

よって、\(dp[i][j][k]\) を、「ケーキ \(i\) まで見たときに、採用されたケーキの数が \(\min(2K, i) - j\) であるようなものであり、それぞれのカテゴリについて、使った回数の偶奇が \(k\) で表現されるものの、価格の最大値」とすると、\(j\) は \(0\) 以上 \(2\) 以下のものだけを探索すれば良くなるため、状態数が \(24N\) の dp をすることで、この問題を解くことができます。

実装例

証明は、ケーキ \(1\) からケーキ \(2K\) のうち、採用されないケーキの数が \(3\) 個であるような最適解が存在したと仮定すると、解を悪くすることなく、前半のケーキの採用されない数を減らすことができることからできます。(WIP)