D - バレンタインデー AtCoder Beginner Contest 018
問題概略
N人の女子とM人の男子がいる。女子はいくつかのチョコを持っており、渡したい男子とその時の幸福度がある。
女子P人と男子R人を選んで幸福度を最大にしたい。
制約
1<=all<=18
解法
愚直にやると 18c9 * 18c9 で 48000 * 48000 ぐらいになる。
片方を固定したくなる。
例えば女子の組が決まっていれば、ある男子を入れた時のスコアが分かる
具体的にはチョコレートを見ていって、対応する女子がグループにいれば男子に加算すればいい
男子の結果は独立しているため、貪欲に選べる
public static void main(String[] args) { //longを忘れるなオーバーフローするぞ N = ni(); M = ni(); P = ni(); Q = ni(); R = ni(); long startTime = System.currentTimeMillis(); int[][] cho = new int[N][M]; for (int i = 0; i < R; i++) { cho[ni() - 1][ni() - 1] = ni(); } for (int bit = 0; bit < (1 << 18); bit++) { if (Integer.bitCount(bit) != P) continue; int[] ma = new int[M]; for (int ni = 0; ni < N; ni++) { for (int mi = 0; mi < M; mi++) { if (bitGet(bit, ni)) { ma[mi] += cho[ni][mi]; } } } revSort(ma); long res = 0; for (int i = 0; i < Q; i++) { res += ma[i]; } chMax(res); } System.out.println(maxRes); long endTime = System.currentTimeMillis(); System.err.println(endTime - startTime); }