CVBB ACM Team

POJ 1191

$8\times8$矩阵切$n-1$次成$n$块（每切一次挑其中一半继续切），问最小均方差

题解：均方差的一种形式是$\sqrt{\frac{\sum{x_i^2}}{n}-{\bar{x}}^2}$，平均值其实是固定的，所以最小化$\sum{x_i^2}$。二维区间dp。

有精度问题要用c++提交才能过g++不行。。恐怖

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,a[9][9];
int f[9][9][9][9][16],pre[9][9];
int dp(int x1,int y1,int x2,int y2,int k)
{
	if(k==0)
	f[x1][y1][x2][y2][k]=(pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1])*(pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1]);
	if(x1==x2&&y1==y2)f[x1][y1][x2][y2][k]=a[x1][y1]*a[x1][y1];
	if(f[x1][y1][x2][y2][k]<0x3f3f3f3f)return f[x1][y1][x2][y2][k];
	for(int i=x1;i<x2;i++)
	{
		f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,y1,i,y2,0)+dp(i+1,y1,x2,y2,k-1));
		f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,y1,i,y2,k-1)+dp(i+1,y1,x2,y2,0));
	}
	for(int i=y1;i<y2;i++)
	{
		f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,y1,x2,i,0)+dp(x1,i+1,x2,y2,k-1));
		f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,y1,x2,i,k-1)+dp(x1,i+1,x2,y2,0));
	}
	return f[x1][y1][x2][y2][k];
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(pre,0,sizeof(pre));
		memset(f,0x3f,sizeof(f));
		for(int i=1;i<=8;i++)
		{
			for(int j=1;j<=8;j++)
			{
				scanf("%d",&a[i][j]);
				pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+a[i][j];
 
			}
		}
		printf("%.3lf\n",sqrt(dp(1,1,8,8,n-1)*1.0/n-(1.0*pre[8][8]/n)*(1.0*pre[8][8]/n)));
	}
	return 0;
}