经典递归问题--棋盘分割 POJ--1191

// 棋盘分割.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

double a[8][8]={0};
int n=0;
double aver_2=0.0;
double dfs(int i,int j,int k,int p,int cnt);
double recorde[16][9][9][9][9]={0};
double sum_record[9][9][9][9]={0};

int main()
{
	//while(scanf("%d",&n)!=EOF)
	scanf("%d",&n);
	{
		memset(recorde,-1,sizeof(recorde));
		memset(sum_record,-1,sizeof(sum_record));

		double sum=0.0;
		double x_aver=0.0;
		double x_i=0.0;

		for(int i=0;i<8;i++)
			for(int j=0;j<8;j++)
			{
				scanf("%lf",&a[i][j]);
				sum+=a[i][j];
			}
		    x_aver=sum/n;
			x_aver*=x_aver;
			aver_2=x_aver;
		    x_i=dfs(0,7,0,7,1);
			double ans=sqrt(x_i/n-x_aver) ;
			//cout<<ans<<endl;
			printf("%0.3f",ans);
	}
	return 0;
}

double sum_(int i,int j,int k,int p)
{
	if(sum_record[i][j][k][p]>=0)
		return sum_record[i][j][k][p];
	int ii=0,kk=0;
	double sum=0.0;
	for(ii=i;ii<=j;ii++)
		for(kk=k;kk<=p;kk++)
			sum+=a[kk][ii];
	sum_record[i][j][k][p]=sum*sum;
	return sum_record[i][j][k][p];
}

double min_(double a,double b)
{
	return (a>b?b:a);
}
double min_1(double a,double b)
{
	return (a/n-aver_2>b/n-aver_2?b:a);
}


double dfs(int i,int j,int k,int p, int cnt)
{
	if(recorde[cnt][i][j][k][p]>=0)
		return recorde[cnt][i][j][k][p];
	int ii=0,kk=0;
	double temp1=0,temp2=0;
	double min=999999999999999;
	if(cnt==n)
	{
		return sum_(i,j,k,p);
	}
	for(ii=i;ii<j;ii++)
	{
		temp1=sum_(i,ii,k,p)+dfs(ii+1,j,k,p,cnt+1);
		if(min>temp1) 
			min=temp1;
		temp2=sum_(ii+1,j,k,p)+dfs(i,ii,k,p,cnt+1);  
		if(min>temp2) 
			min=temp2;
	}
	
	for(kk=k;kk<p;kk++)
	{
		temp1=sum_(i,j,k,kk)+dfs(i,j,kk+1,p,cnt+1);
		if(min>temp1) 
			min=temp1;
		temp2=sum_(i,j,kk+1,p)+dfs(i,j,k,kk,cnt+1);  
		if(min>temp2) 
			min=temp2;
	}
	recorde[cnt][i][j][k][p]=min;
	return min;
}