解説

以下、$K$ 個の宝石を選ぶ方法があるとして進めます。

まず、明らかに昇順または降順に宝石を並べるのが最適です。 このとき、そのネックレスの不均一さは必ず、最初と最後の宝石の綺麗さの差と等しくなります。

よって、

• $\mathrm{min\_dp}[s] = \text{選ぶ宝石が集合 s で表される時の、宝石の綺麗さの最小値}$
• $\mathrm{max\_dp}[s] = \text{選ぶ宝石が集合 s で表される時の、宝石の綺麗さの最大値}$

以上の $2$ つを、重さの制約に気を付けながら更新します。 そして $\mathrm{popcount}(s) = K$ であるような $s$ 全てについて $\mathrm{max\_dp}[s] - \mathrm{min\_dp}[s]$ の最小値が解となります。

計算量は実装によりますが、$Ο(2^NN)$ 程度で可能です。

なお、bit 全探索を用いても同様に解くことができます。