https://emtubasa.hateblo.jp/entry/2019/05/23/013716

解法

制約から見てbitDPです。

$dp[S] =$ 現在グループを組めていないウサギの状態が $S$ のときに、それ以降のグループ分けで得ることができる得点の最大値

とします。すると、 $S$ の部分集合 $T$ を用いて、
$dp[S] = max(dp[S\setminus T ] + sum[T])$
と書くことができます。
ただし、 $sum[T]$ は、 $T$ というグループを作成したときに得られる得点です。これは、前計算によって $O(2^{N}N^{2})$ で計算できます。
先ほどのDPの遷移の計算量を見積もってみます。
ある集合 $S$ について、残っているウサギの数を $|S|$ と表現すると、部分集合 $T$ は $2^{|S|}$ 通りあります。
残っているウサギの数が $|S|$ となるような集合 $S$ の選び方は $_{N}C_{|S|}$ です。ここで、本来は $|S|$ が0となるような選び方をしないのですが、計算をしやすくするために0も選ぶことができるとすると、 $|S|$ が $0$ から $N$ まであり得ることに注意して、
$\displaystyle \sum_{i=0}^{N} 2^{i} \ _{N}C_{i}$
となり、これは
$\displaystyle \sum_{i=0}^{N} 2^{i} \times 1^{N-i} \times _{N}C_{i}$
であり、結局二項定理の式そのものなので、
$(2+1)^{N} = 3^{N}$
となります。
ということで、最初のDPの遷移は $O(3^{N})$ で計算できるということがわかりました。
あとは、前計算とDPの遷移を行うことで、 $dp[S_{all}]$ を見れば答えがわかります( $S_{all}$ は全てのウサギが入っている状態です)。初期状態は、ウサギが1羽の任意の集合 $U$ に対して、 $dp[U] = 0$ です。

$S$ の部分集合列挙は、

for(int b = S; b > 0; --b &= S){
  hoge;
}

という感じでやるとできます。
桁が下の方から削除していくイメージです。

感想

だいぶ前に考察だけ終わらせておいて放置していた問題でした…
bitDPなのでやりたいことはほぼ覚えてました。一見 $O(4^{N})$ になりそうで、きちんと計算すると計算量が減るタイプの問題ですね。