[NOI1999] 棋盘分割

2023-11-28 23:51:04

【NOI1999】棋盘分割

题目描述

将一个 \(8 \times 8\) 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了 \((n−1)\) 次后，连同最后剩下的矩形棋盘共有 \(n\) 块矩形棋盘。 (每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 \(n\) 块矩形棋盘，并使各矩形棋盘总分的均方差最小。

均方差 \(\sigma=\sqrt{\dfrac{\sum^{n}_{i=1}\times(x_i-\bar x)^2}{n}}\)，其中平均值 \(\bar x=\dfrac{\sum_{i=1}^{n}x_i}{n}\),\(x_i\) 为第 \(i\) 块矩形棋盘的分。

请编程对给出的棋盘及 \(n\)，求出 \(\sigma\) 的最小值。

输入格式

第一行为一个整数 \(n(1<n<15)\)。

第二行至第九行每行为 \(8\) 个小于 \(100\) 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出格式

仅一个数，为 \(\sigma\) （四舍五入精确到小数点后三位）。

题目分析

终于从 y 总那里听懂了，于是赶快来写篇题解。

一道区间 DP。

设平均值 \(\bar x = \dfrac{\sum_{i=1}^{n}x_i}{n}\)，

方差 \(\sigma = \sqrt{\dfrac{\sum_{i=1}^{n}\times (x_i-\bar x)^2}{n}}\)

由于我们要使方差 \(\sigma\) 最小，那么不妨将方差平方后再进行化简（过程我会写的有些繁琐，可以跳着看）：

\(\sigma^2=\dfrac{\sum_{i=1}^{n}\times (x_i-\bar x)^2}{n}\)

\(\sigma^2=\dfrac{1}{n}\times (\sum_{i=1}^{n}\times({x_i}^2 +{\bar x}^2 - 2\times x_i\times \bar x))\)

\(\sigma^2 = \frac{1}{n}(\sum_{i=1}^n{x_i}^2 - 2\sum_{i=1}^nx_i\times\bar{x} + \sum_{i=1}^n\bar{x}^2)\)

\(\sigma^2 = \frac{1}{n}\sum_{i=1}^nx_i^2 - 2\bar{x}\times\frac{1}{n}\sum_{i=1}^nx_i + \frac{1}{n}\times n\bar{x}^2\)

发现第二项的 \(\frac{1}{n}\sum_{i=1}^nx_i\) 正好就是 \(\bar x\)，于是：

\(\sigma^2 = \frac{1}{n}\sum_{i=1}^nx_i^2 - 2\overline{x}^2 + \bar{x}^2\)

\(\sigma^2 = \frac{1}{n}\sum_{i=1}^nx_i^2 - \bar{x}^2\)

\(\bar x\) 很明显是一个可以马上求出的数，并且我们需要频繁地求矩阵和，所以考虑使用二维前缀和 \(O(1)\) 查询矩阵和，大大加快了效率。

在这篇题解中，我们采用 \((x1,y1,x2,y2)\) 的方式表示一个矩阵，其左上角为 \((x1,y1)\)，右下角为 \((x2,y2)\)。

令 \(dp[a][b][c][d][k]\) 表示划分到 \(k-1\) 个的子矩阵，是以 \((a,b)\) 为左上角，\((c,d)\) 为右下角。

我们可以采用记忆化方法来完成此过程。

//2021/8/9

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#define debug(c) cerr<<#c<<"="<<c<<endl

using namespace std;

const int ma=10,maxn=16;

const double INF=1e9;

int n;

int sum[ma][ma];

double dp[ma][ma][ma][ma][maxn];

double bar;//平均值 

//如果是C++11可以这样，但是有些编译器因为这里又有cmath又有y1 y2，会CE 
//当然就算报错，换个名就好了
 
inline double getsum(int x1,int y1,int x2,int y2)
{
	double res=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]-bar;
	
	return res*res;
}

inline double dfs(int x1,int y1,int x2,int y2,int k)//记忆化方法 
{
	double &tmp=dp[x1][y1][x2][y2][k];
	
	if(tmp>=0)
	{
		return tmp;
	}
	
	if(k==1)
	{
		return getsum(x1,y1,x2,y2);
	}
	
	tmp=INF;
	
	//横着去切 
	
	for(register int i=x1;i<x2;i++)
	{
		tmp=min(tmp,dfs(x1,y1,i,y2,k-1)+getsum(i+1,y1,x2,y2));
		
		tmp=min(tmp,dfs(i+1,y1,x2,y2,k-1)+getsum(x1,y1,i,y2)); 
	}
	
	//竖着去切 
	
	for(register int i=y1;i<y2;i++)
	{
		tmp=min(tmp,dfs(x1,y1,x2,i,k-1)+getsum(x1,i+1,x2,y2));
		
		tmp=min(tmp,dfs(x1,i+1,x2,y2,k-1)+getsum(x1,y1,x2,i));
	}
	
	return tmp;
}

int main(void)
{
	scanf("%d",&n);
	
	for(register int i=1;i<=8;i++)
	{
		for(register int j=1;j<=8;j++)
		{
			scanf("%d",&sum[i][j]);
			
			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	
	memset(dp,-1,sizeof(dp));
	
	bar=(double)sum[8][8]/n;
	
	printf("%.3lf\n",sqrt(dfs(1,1,8,8,n)/n));
	
	return 0;
}

码农公寓