题解 P5752 【[NOI1999]棋盘分割】

zhangboju · 2020-04-07 22:00:31 · 题解

Update: 感谢 zhangtianhan 指出的错误（将方差与标准差混淆），已纠正。

\LaTeX 有点锅，请在 blog 查看

题目传送门：Link

这个题目很重要的条件就是：

每次切割都只能沿着棋盘格子的边进行。

关于这个条件的解释，题面中已经写的很清楚了，我就不赘述了。

考虑使均方差 \sigma=\sqrt{\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n}} 最小

则考虑使方差 \sigma^2=\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n} 最小

分析得到 \bar{x}=\dfrac{\sum\limits_{i=1}^nx_i}{n} 无论 x_i 的取值 ，\bar{x} 恒等于 \dfrac{\sum\limits_{i=1}^8\sum\limits_{j=1}^8w_{i,j}}{n}，其中 w_{i,j} 代表每一个格子上的数。

所以可以预处理 \bar{x}。

此时可以发现将每个 x_i 分开考虑，使得 \dfrac{(x_i-\bar{x})^2}{n} 最小，即考虑使用动态规划。

由于此题是一个比较明显的区间分割问题，考虑使用区间 DP。

令 f_{x_1,y_1,x_2,y_2,k} 表示将以 (x_1,y_1) 为左上角，以 (x_2,y_2) 为右下角的子矩阵划分为 k 个子矩阵的最小方差 \sigma^2，则最终答案为 \sqrt{f_{1,1,8,8,n}}。

此时我们发现要计算子矩阵的和，则考虑二维前缀和。定义 s_{i,j}=\sum\limits_{q=1}^{i}\sum\limits_{w=1}^{j}w_{q,w}。

二位前缀和写法这里不赘述。

利用 s_{i,j}，可 O(1) 求出子矩阵的和。

首先定义 {get}(x_1,y_1,x_2,y_2)=\dfrac{((\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}w_{i,j})-\bar{x})^2}{n}

边界 k=1 时，f_{x_1,y_1,x_2,y_2,1}={get}(x_1,y_1,x_2,y_2)。

在状态转移时，分类讨论水平切还是竖直切，枚举在哪里切，再分类讨论是要哪一块。

若横向切割：

枚举 i \in [x_1,x_2) 表示将第 i 行和第 i+1 行分开，则新的到的两个矩阵左上角和右下角坐标如上图所示。

若选取上半部分进行再次划分，则 f_{x_1,y_1,x_2,y_2,k}=f_{x_1,y_1,i,y_2,k-1}+{get}(i+1,y_1,x_2,y_2)。

若选取下半部分进行再次划分，则 f_{x_1,y_1,x_2,y_2,k}=f_{i+1,y_1,x_2,y_2,k-1}+{get}(x_1,y_1,i,y_2)。

若纵向切割：

枚举 i \in [y_1,y_2) 表示将第 i 列和第 i+1 列分开，则新的到的两个矩阵左上角和右下角坐标如上图所示。

若选取上半部分进行再次划分，则 f_{x_1,y_1,x_2,y_2,k}=f_{x_1,y_1,x_2,i,k-1}+{get}(x_1,i+1,x_2,y_2)。

若选取下半部分进行再次划分，则 f_{x_1,y_1,x_2,y_2,k}=f_{x_1,i+1,x_2,y_2,k-1}+{get}(x_1,y_1,x_2,i)。

令 f_{x_1,y_1,i,y_2,k-1}+{get}(i+1,y_1,x_2,y_2) 为 (1)；