本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 20:47:48

谨此纪念我的第一道蓝题题解（虽然是看了其他题解后写的）

题意

给定一个序列 $W_0 \cdots W_{n - 1}$，以及一个整数 $D$，要求把 $W$ 的所有元素分配到 $D$ 个盒子中，求分配的方差和最小值。

分析

很明显是动态规划题。我们可以设 $f(i,j)$，表示将状态 $j$ 所表示的元素分配到 $i$ 个盒子中的最小方差（$\sum_k^i (x_k-\bar x)^2$）。

分析边界：

$f(0,j)$，也就是将所有元素放到同一个盒子中，就是： $$f(i, j)=\sum\limits_k^0 (x_k-\bar x)^2=(x_k-\bar x)^2 \quad i = 0$$

对于一般情况，要将 $j$ 所表示的元素放进 $i$ 个盒子中，我们要考虑 $j$ 的每个子状态 $k$：找将 $s$ 与 $k$ 差的元素放进 $i - 1$ 个盒子中所得到的最小方差和再加上 $k$ 状态的方差，以上的最小值，也就是

$$f(i, j) = \min\limits_{k\in j}{f(i-1,j\oplus k)+(x_k-\bar x)^2}$$

因此

$$f(i,j) = \begin{cases} (x_j - \bar x)^2 & i = 0 \ \min\limits_{k\in j} f(i-1,j\oplus k)+(x_k - \bar x)^2 & \text{otherwise} \end{cases}$$

证明

证明是彻底理解转移方程原理的很好方式。

首先易证本问题有最优子结构：

最优子结构证明

问题就是求 $\frac{1}{D}\min\sum\limits_{i=0}^D(x_i-\bar x)^2$。设 $T$ 是问题的最优解，要证 $\sum\limits_{i=1}^D(T_i-\bar x)^2$ 也最小。

反证。设 $U_1,\cdots,U_{D-1}$ 是一个更优的方案，即

$$ \sum\limits_{i=1}^D(T_i-\bar x)^2 > \sum\limits_{i=1}^D(U_i -\bar x)^2 $$

那么可以有

$$ T' = \frac{1}{D}((T_1-\bar x)^2+\sum\limits_{i=1}^D(U_i-\bar x)^2) $$

则必有 $T' < T$，与 $T$ 是本问题的最优解冲突。故不存在比 $T_1, \cdots T_{D-1}$ 更优的方案 $U$，得证。

以上是证明最优子结构的常用方法，即《算法导论》中所讲的 copy-paste 法。

代码

代码预计算出了 $\bar x$ 与 每一种状态 $k$ 对应的 $x_k$，然后就是状压 DP。

#include <iostream>
using namespace std;

#define rep(v, s, e) for (auto v = (s); v < (e); v++)
#define square(x) ((x) * (x))
const int N = 15, M = 1 << 15;

long long *w;
long long s[M];
double f[N][M];

long long
read (void)
{
  long long res = 0;
  char c;

  while (!isdigit (c = getchar ()));
  do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
  return res;
}

int
main (void)
{
  int n, d; n = read (); d = read ();
  double xbar = 0;

  w = new long long [n];
  
  rep (i, 0, n) xbar += w[i] = read ();
  xbar \/= d;

  rep (i, 0, 1 << n) rep (j, 0, n + 1)
    s[i] += w[j] * !!(i & (1 << j));

  rep (i, 0, 1 << n) f[0][i] = square (s[i] - xbar);
  rep (i, 1, d) rep (j, 0, 1 << n)
    {
      f[i][j] = f[i - 1][j] + square (xbar);
      for (int k = j; k; k = (k - 1) & j)
	f[i][j] = min (f[i][j], f[i - 1][j ^ k] + square (s[k] - xbar));
    }

  printf ("%.10lf\n", f[d - 1][(1 << n) - 1] \/ d);
  return 0;
}

补充最优解

以上代码 不是最优解 （235ms）。

最优解使用的是另一种动态规划的实现方法，即自上到下的动态规划。在某些情况下这可以省去很多的计算。采用这种方法可以得到 13ms 的最优解。

upd. 2023/12/15 增加最优解

证明有错误或叙述不当的请指出。感谢。