SRM 478 div1 med:KiwiJuice
微妙に理由わかってないんですが解説ないのでうーん。ていうかこれ…
解法
理由がよくわからないんですが, ある集合 s を選んで, その集合同士でのみジュースのやり取りをした場合, 必ずジュースの量の割り当ては以下のようになります。
sum がその集合のジュースの合計量であるとして, sum/C 個, 容量が C のジュースになり, 1 つ sum%C のジュースがあり, あとはすべて 容量が 0 のジュースになります。
よって, dp[s] = (集合 s から得られる利益の最大値)とすれば, s からジュースをやり取りする集合 sub を選んで, sub について得られる利益を調べた後, 残りの集合 s^sub で得られる利益を dp[s^sub] で調べます。これらの和の最大値が dp[s] です。
s の部分集合 sub 蟻本の 144 ページに書いてあるような要領で全列挙することが出来ます。部分集合を調べるのに 2^n の計算量を書ける必要はないです。
計算量を解析します。要素の数が k 個の部分集合を列挙するのは, O(2^k) かかるので, 全体の計算量は,
comb[15][k] * 2^(15-k) の和です。ただし, comb[n][r] は nCr を表します(伝われ)。
これは 3^k に等しいです。およそ 1.4*10^7 なので十分間に合います。下のコードでは少し手抜きして この 15 倍の計算量がかかりますが普通に間に合いました。
int dp[1<<16]; int dfs(int s, const int C, const vi& bottles, const vi& prices) { int& ret = dp[s]; if (ret >= 0) return ret; if (s == 0) return ret = 0; int sub = s, n = bottles.size(); ret = 0; do { int ns = s^sub; int tmp = dfs(ns, C, bottles, prices); int cnt = 0, sum = 0; for (int i = 0; i < n; i++) { if ((sub>>i)&1) { sum += bottles[i]; cnt++; } } for (int i = 0; i < cnt; i++) { if (sum >= C) { tmp += prices[C]; sum -= C; } else { tmp += prices[sum]; sum = 0; } } ret = max(ret, tmp); sub = (sub-1)&s; } while (sub != s); return ret; } class KiwiJuice { public: int theProfit(int C, vector <int> bottles, vector <int> prices) { int n = bottles.size(); memset(dp, -1, sizeof(dp)); return dfs((1<<n)-1, C, bottles, prices); } };