[ABC332E] Lucky bag 题解

· · 题解

先推一推式子：

\begin{aligned} V &=\frac{1}{D}\sum_{i=1}^D(x_i-\overline{x})^2\\ &=\frac{1}{D}\sum_{i=1}^Dx_i^2-2\overline{x}x_i+\overline{x}^2\\ &=\frac{1}{D}\left(\sum_{i=1}^Dx_i^2\right)-2\overline{x}\frac{1}{D}\left(\sum_{i=1}^Dx_i\right)+\overline{x}^2\\ &=\frac{1}{D}\left(\sum_{i=1}^Dx_i^2\right)-2\overline{x}^2+\overline{x}^2\\ &=\frac{1}{D}\left(\sum_{i=1}^Dx_i^2\right)-\overline{x}^2\\ \end{aligned}

于是你只需要最小化 \displaystyle\sum_{i=1}^Dx_i^2。

考虑状压 dp，设 f_{i,S} 表示现在已经分出了 i 组，且集合 S 内的数已经被选走了时的最小的 \displaystyle\sum_{j=1}^ix_j^2。有转移方程：

f_{i,S}=\min_{T\subseteq S}\left\{f_{i-1,T}+\left(\sum_{j\in S\setminus T}W_j\right)^2\right\}

直接做即可，时间复杂度 \mathcal{O}(D3^N)。

特别要注意的是你输出答案时应当只在最后进行一次 long double 下的除法，之前的运算都应在整数下进行，否则精度误差能直接给你爆了。

#include <iomanip>
#include <iostream>

using namespace std;
using LL = long long;

const int kN = 15;

int n, d, w[kN];
LL f[kN + 1][1 << kN], s[1 << kN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> d;
  for (int i = 0; i < n; ++i) {
    cin >> w[i];
    for (int j = 0; j < (1 << n); ++j) {
      if (j >> i & 1) {
        s[j] += w[i];
      }
    }
  }
  for (int i = 0; i < (1 << n); ++i) {
    s[i] *= s[i];
  }
  for (int i = 1; i < (1 << n); ++i) {
    f[0][i] = 3e18;
  }
  for (int i = 1; i <= d; ++i) {
    for (int j = 0; j < (1 << n); ++j) {
      f[i][j] = s[j];
      for (int k = j; k; k = j & k - 1) {
        f[i][j] = min(f[i][j], f[i - 1][k] + s[j ^ k]);
      }
    }
  }
  cout << fixed << setprecision(15) << 1.0L * (f[d][(1 << n) - 1] * d - s[(1 << n) - 1]) / (d * d);
  return 0;
}