#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>

int d[16][9][9][9][9],s[9][9][9][9],mtr[9][9],ss[9][9];

int MIN(int a ,int b)
{
	if(a<b)return a;
	else return b;
}
int main()
{
	int i,n,k,j,a,temp=0,sum=0,x1,x2,y1,y2;
	double ave,tot=0;
	scanf("%d",&n);
	for(i=0;i<8;++i)
	{
		for(j=0;j<8;++j)
		{
			scanf("%d",&mtr[i][j]);
			sum+=mtr[i][j];
			tot+=mtr[i][j];
			if(!i)ss[i][j]=sum;
			else ss[i][j]=ss[i-1][j]+sum;
			if(j==7)sum=0;
		}
	}
	ave=tot/n;
	for(x1=0;x1<8;++x1)
		for(y1=0;y1<8;++y1)
			for(x2=x1;x2<8;++x2)
				for(y2=y1;y2<8;++y2)
				{
					if(x1==0||y1==0)temp=ss[x2][y2];
					else
					temp=ss[x2][y2]+ss[x1-1][y1-1]-ss[x1-1][y2]-ss[x2][y1-1];
					s[x1][y1][x2][y2]=temp*temp;
					d[0][x1][y1][x2][y2]=s[x1][y1][x2][y2];
				}
/* 	 for (x1=0; x1<8; x1++)  
   {  
        for (y1=0; y1<8; y1++)  
        {  
            for (x2=x1; x2<8; x2++)  
            {  
                sum = 0;  
                for (y2=y1; y2<8; y2++)  
                {  
                    sum += mtr[x2][y2];  
                    if (x2 == x1)  
                    {  
                        s[x1][y1][x2][y2] = sum;  
                    }  
                    else  
                    {  
                        s[x1][y1][x2][y2] = s[x1][y1][x2-1][y2] + sum;  
                    }  
                       s[x1][y1][x2][y2] *= s[x1][y1][x2][y2];
                    d[0][x1][y1][x2][y2] = s[x1][y1][x2][y2] ;  
                }  
            }  
        }  
    } */ 
	for(k=1;k<=n;++k)
		for(x1=0;x1<8;++x1)
			for(y1=0;y1<8;++y1)
				for(x2=x1;x2<8;++x2)
					for(y2=y1;y2<8;++y2)
					{
						d[k][x1][y1][x2][y2]=2000000000;
						for(i=x1;i<x2;++i)//横切
						{
							d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][x1][y1][i][y2]+s[i+1][y1][x2][y2]);
							d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][i+1][y1][x2][y2]+s[x1][y1][i][y2]);
						}
						for(i=y1;i<y2;++i)//竖切
						{
							d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][x1][y1][x2][i]+s[x1][i+1][x2][y2]);
							d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][x1][i+1][x2][y2]+s[x1][y1][x2][i]);
						}
					}

 /*for (k=1; k<=n-1; k++)  
    {  
        for (x1=0; x1<8; x1++)  
        {  
            for (y1=0; y1<8; y1++)  
            {  
                for (x2=x1; x2<8; x2++)  
                {  
                    for (y2=y1; y2<8; y2++)  
                    {  
                        d[k][x1][y1][x2][y2] = 2000000000;  
                        for (a=x1; a<x2; a++)  
                        {  
                            temp = MIN(d[k-1][x1][y1][a][y2] + s[a+1][y1][x2][y2],   
                                        d[k-1][a+1][y1][x2][y2] + s[x1][y1][a][y2]);  
                            d[k][x1][y1][x2][y2] = MIN(d[k][x1][y1][x2][y2], temp);  
                        }  
                          
                        for (a=y1; a<y2; a++)  
                        {  
                            temp = MIN(d[k-1][x1][y1][x2][a] + s[x1][a+1][x2][y2],  
                                        d[k-1][x1][a+1][x2][y2] + s[x1][y1][x2][a] );  
                            d[k][x1][y1][x2][y2] = MIN(d[k][x1][y1][x2][y2], temp);  
                        }  
                    }  
                }  
            }  
        }  
    }  
	*/
	double ret = sqrt((double)d[n-1][0][0][7][7]/(double)n-ave*ave);
	printf("%.3f\n",ret);
	return 0;
}

• Re:拜托哪个善良的牛人帮我看一下，为什么那个s数组求得不对啊！？明明这个道理很对啊！aUb=a+b-a^b啊 (3771) 1412611 2016-11-07 18:27:05