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

· · 题解

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)

$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)); } ```