ABC018 D - バレンタインデー - ツバサの備忘録

解法

部分点が、どうせ男女の組み合わせについてすべてのパターンを試すんだろうなぁ、という感じがしたので、どうせ男子か女子どちらかのみを探索すると答えを求めるようにすることで高速化をするのかなぁ、という気持ちになります。
ということで、女子の組み合わせの全てのパターンを調べて、幸福度の最大値を求めることについて考えてみます。
まず、女子の組み合わせは $_N C _P$ で求められるので、だいたい $10^4$ 程度で調べられます(計算ミスしてたらごめんなさい)。
さて、ある女子の組み合わせに対する幸福度の最大値は、DPで求めることができます。
ある女子の組み合わせに対して、出席番号が $i$ 番目の男子を旅行グループに入れたときに増える幸福度を前計算で求めると、これは $O(N)$ で求めることができます。 $j$ 番の女子が旅行グループにいて、かつ $i$ 番の男子に対してのチョコを持っていた場合に幸福度を加算していけばよいです。これを $z$ とします。
$dp[i][j]=i$ 番までの男子から、 $j$ 人選んだ場合につくれる幸福度の最大値
とすると、よくあるDPになります。
$dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+z)$
となり、今調べている女子の組み合わせに対する幸福度の最大値は、 $dp[M][Q]$ になります。このDPは $O(MQ)$ になります。
あとは、全ての女子の組み合わせに対して幸福度の最大値を求め、その中でも一番大きいものを選べば、答えになります。
女子の組み合わせを選ぶときは、ビットで状態を持ち、再帰をすると書きやすいかなぁと思います。