题解 P5752 【[NOI1999]棋盘分割】
zhangboju
2020-04-07 22:00:31
Update: 感谢 [zhangtianhan](https://www.luogu.com.cn/user/226176) 指出的错误（将方差与标准差混淆），已纠正。
[$\LaTeX$ 有点锅，请在 blog 查看](https://www.luogu.com.cn/blog/zhangboju/solution-p5752)
题目传送门：[Link](https://www.luogu.com.cn/problem/P5752)
这个题目很重要的条件就是：
> 每次切割都只能沿着棋盘格子的边进行。
关于这个条件的解释，题面中已经写的很清楚了，我就不赘述了。
考虑使均方差 $\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)$；
$f_{i+1,y_1,x_2,y_2,k-1}+{get}(x_1,y_1,i,y_2)$ 为 $(2)$；
$f_{x_1,y_1,x_2,i,k-1}+{get}(x_1,i+1,x_2,y_2)$ 为 $(3)$；
$f_{x_1,i+1,x_2,y_2,k-1}+{get}(x_1,y_1,x_2,i)$ 为 $(4)$。
则可得出状态转移方程：
$$
f_{x_1,y_1,x_2,y_2,k}=\min(\min\limits_{x_1\leq i<x_2}((1),(2))\ \ ,\min\limits_{y_1\leq i< y_2}((3),(4)))
$$
----------
总时间复杂度 $O(8^5n)$。
由于循环太多，采用记忆化搜索写。
代码中 `X` 即为 $\bar{x}$。
注意 `X` 计算时别忘了强制转换 `s` 数组的类型。
```cpp
#include<bits/stdc++.h>
using namespace std;
double f[9][9][9][9][15];
int s[9][9];
double X;
int n;
double get(int x_1,int y_1,int x_2,int y_2)
{
double sum=s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]-X;
return sum*sum/n;
}
double dp(int x_1,int y_1,int x_2,int y_2,int k)
{
if(f[x_1][y_1][x_2][y_2][k]>=0) return f[x_1][y_1][x_2][y_2][k];
if(k==1) return f[x_1][y_1][x_2][y_2][k]=get(x_1,y_1,x_2,y_2);
f[x_1][y_1][x_2][y_2][k]=1e9;
for(int i=x_1;i<x_2;i++)
{
f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],dp(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]=min(f[x_1][y_1][x_2][y_2][k],dp(i+1,y_1,x_2,y_2,k-1)+get(x_1,y_1,i,y_2));
}
for(int i=y_1;i<y_2;i++)
{
f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],dp(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]=min(f[x_1][y_1][x_2][y_2][k],dp(x_1,i+1,x_2,y_2,k-1)+get(x_1,y_1,x_2,i));
}
return f[x_1][y_1][x_2][y_2][k];
}
int main()
{
cin>>n;
for(int i=1;i<=8;i++)
{
for(int j=1;j<=8;j++)
{
scanf("%lf",&s[i][j]);
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
memset(f,-1,sizeof f);
X=(double)s[8][8]/n;
printf("%.3lf\n",sqrt(dp(1,1,8,8,n)));
}
```
这个 `memset` 是一个很玄学的东西，害的我调了半天。
于是我还是写了一份循环的：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define x1 x_1
#define x2 x_2
#define y1 y_1
#define y2 y_2
double f[9][9][9][9][15];
int s[9][9];
double X;
int n;
inline double get(int x1,int y1,int x2,int y2)
{
double sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]-X;
return sum*sum/n;
}
int main()
{
cin>>n;
for(int i=1;i<=8;i++)
{
for(int j=1;j<=8;j++)
{
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
X=(double)s[8][8]/n;
for(int k=1;k<=n;k++)
{
for(int x1=1;x1<=8;x1++)
{
for(int y1=1;y1<=8;y1++)
{
for(int x2=1;x2<=8;x2++)
{
for(int y2=1;y2<=8;y2++)
{
f[x1][y1][x2][y2][k]=1e9;
if(k==1)
{
f[x1][y1][x2][y2][k]=get(x1,y1,x2,y2);
continue;
}
for(int i=x1;i<x2;i++)
{
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[x1][y1][i][y2][k-1]+get(i+1,y1,x2,y2));
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[i+1][y1][x2][y2][k-1]+get(x1,y1,i,y2));
}
for(int i=y1;i<y2;i++)
{
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[x1][y1][x2][i][k-1]+get(x1,i+1,x2,y2));
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[x1][i+1][x2][y2][k-1]+get(x1,y1,x2,i));
}
}
}
}
}
}
printf("%.3lf\n",sqrt(f[1][1][8][8][n]));
}
```
再次强调 $f_{x_1,y_1,x_2,y_2,k}$ 是存储的将子矩阵 $(x_1,y_1)(x_2,y_2)$ 划分为 $k$ 个子矩阵的最小**方差** $\sigma^2$，**所以最后还要开根号！**
------------
当然，这个题还可以采用其他方法。
同样考虑使**方差** $\sigma^2=\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n}$ 最小。
拆开平方：$\sigma^2=\dfrac{1}{n}[\sum\limits_{i=1}^n(x_i^2-2x_i\bar{x}+\bar{x}^2)]$。
拆开括号：$\sigma^2=\dfrac{1}{n}(\sum\limits_{i=1}^nx_i^2-2\bar{x}\sum\limits_{i=1}^nx_i+n\bar{x}^2)=\dfrac{\sum\limits_{i=1}^nx_i^2}{n}-2\bar{x}\dfrac{\sum\limits_{i=1}^nx_i}{n}+\bar{x}^2$。
而我们知道：$\bar{x}=\dfrac{\sum\limits_{i=1}^nx_i}{n}$。
所以：$\sigma^2=\dfrac{\sum\limits_{i=1}^nx_i^2}{n}-\bar{x}^2$。
要使 $\sigma^2$ 最小，由于 $\bar{x}^2$ 为定值，则使 $\dfrac{\sum\limits_{i=1}^nx_i^2}{n}$ 最小。
--------------
此时改变 $f_{x_1,y_1,x_2,y_2,k}$ 的意义，表示将以 $(x_1,y_1)$ 为左上角，以 $(x_2,y_2)$ 为右下角的子矩阵划分为 $k$ 个子矩阵的最小的 $\dfrac{\sum\limits_{i=1}^kx_i^2}{n}$。
改变 ${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})^2}{n}$。
则最后答案为 $\sqrt{f_{1,1,8,8,n}-\bar{x}^2}$。
状态转移方程不变。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define x1 x_1
#define x2 x_2
#define y1 y_1
#define y2 y_2
double f[9][9][9][9][15];
int s[9][9];
double X;
int n;
inline double get(int x1,int y1,int x2,int y2)
{
double sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
return sum*sum/n;
}
int main()
{
cin>>n;
for(int i=1;i<=8;i++)
{
for(int j=1;j<=8;j++)
{
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
X=(double)s[8][8]/n;
for(int k=1;k<=n;k++)
{
for(int x1=1;x1<=8;x1++)
{
for(int y1=1;y1<=8;y1++)
{
for(int x2=1;x2<=8;x2++)
{
for(int y2=1;y2<=8;y2++)
{
f[x1][y1][x2][y2][k]=1e9;
if(k==1)
{
f[x1][y1][x2][y2][k]=get(x1,y1,x2,y2);
continue;
}
for(int i=x1;i<x2;i++)
{
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[x1][y1][i][y2][k-1]+get(i+1,y1,x2,y2));
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[i+1][y1][x2][y2][k-1]+get(x1,y1,i,y2));
}
for(int i=y1;i<y2;i++)
{
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[x1][y1][x2][i][k-1]+get(x1,i+1,x2,y2));
f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],f[x1][i+1][x2][y2][k-1]+get(x1,y1,x2,i));
}
}
}
}
}
}
printf("%.3lf\n",sqrt(f[1][1][8][8][n]-X*X));
}
```