ABC#018 D.バレンタインデー

その他

問題

女子N人、男子M人いて、ここから女子P人、男子Q人だけ選ばれてチョコを渡すことが許される。
前もって、ある女子からある男子へプレゼンを渡したときの幸福度の情報が与えられる。
選ばれた男女の幸福度の合計値の最大値を答える。

N,M<=18
P<=N, Q<=M

考え方

女子について、N人からP人選ぶ。
すると、男子側は選ばれた女子から各男子の幸福度が計算できる。
幸福度の高い男子からQ人選べばよい。


という感じだけど、DPを解く週間なので、M人の男子からQ人選んだ場合の最大の幸福度を
dp[i][j]:=i人目まで処理したとき、j人選ばれたときの幸福度最大値
みたいなことをしてO(M^2)を書いた。