SRM 536 div1 easy: MergersDivOne
解法
先に併合されるものほど, 影響が小さくなります。よって, 以下のような解法で解けます。
まず小さい順にソートして, dp をします。dp[i] = (i 番目までで得られる平均値の最大値) とすると, dp[i] は,
- dp[0] = revenue[0]
- dp[k] = max( (dp[i]+revenue[i+1]+...+revenue[k])/(k-i+1) ) (i = 0, 1, ..., k-1)
で出来ます。
公式 editorial 見たら「全部 2 つで平均取るのが良い」って書いてあって確かにそっちのほうが簡潔なんですが, こっちのほうが何も考えないで出来て僕は安心できます。
double dp[55]; double INF = 1e9; class MergersDivOne { public: double findMaximum(vector <int> revenues) { int n = revenues.size(); sort(revenues.begin(), revenues.end()); for (int i = 0; i <= n; i++) dp[i] = -INF; dp[0] = revenues[0]; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { double average = dp[i]; for (int k = i+1; k <= j; k++) average += revenues[k]; average /= j-i+1; dp[j] = max(dp[j], average); } } return dp[n-1]; } };