题目中文不解释了。
刚开始做这题，我想到的就是递归.因为子问题与大问题完全一样..
于是连公式都未化简，写了个递归程序。测试的时候发现n越大,我的程序就很慢才得出结果了..
递归的函数是这么写的
double getMinr(int mini,int maxi,int minj,int maxj,int k) // 表示这个矩形块分割成k块的最小均方差.
double getMinr(int mini,int maxi,int minj,int maxj,int k,int sum)
{
int s=0;
double minr=0x7fffffff,res;
if(k==1)
{
return (sum-xb)*(sum-xb)/n;
}
for(int i=mini+1;i<maxi;i++)
{
s=0;
for(int l=mini;l<i;l++)
for(int m=minj;m<maxj;m++)
s+=chess[l][m];
res=getMinr(mini,i,minj,maxj,k-1,s)+(sum-s-xb)*(sum-s-xb)/n;
if(res<minr) minr=res;
res=getMinr(i,maxi,minj,maxj,k-1,sum-s)+(s-xb)*(s-xb)/n;
if(res<minr) minr=res;
}
for(int i=minj+1;i<maxj;i++)
{
s=0;
for(int l=mini;l<maxi;l++)
for(int m=minj;m<i;m++)
s+=chess[l][m];
res=getMinr(mini,maxi,minj,i,k-1,s)+(sum-s-xb)*(sum-s-xb)/n;
if(res<minr) minr=res;
res=getMinr(mini,maxi,i,maxj,k-1,sum-s)+(s-xb)*(s-xb)/n;
if(res<minr) minr=res;
}
return minr;
}结果发现测试数据时候，发现会超时.
所以开始采用记忆化搜索.并且发现公式可以化简 (xi-xb)*(xi-xb) =xi*xi-2*xi*xb+xb*xb 最后可以将
均方差的平方刚好等于 sum(xi*xi)/n-xb*xb
并且在搜索前记录好值.
这时候代码如下所示。依然TLE...
#include<iostream>
#include<cmath>
using namespace std;
int chess[8][8],n;
int minresult[15][9][9][9][9];//保存结果
int sm[9][9]; //表示从1行1列到i行j列所有数据的总和.
const int INF=10000000;
int getMinr(int mini,int maxi,int minj,int maxj,int k)
{
int s=0,sum=0;
int res,minr=INF;
sum=sm[maxi][maxj]-sm[mini][maxj]-sm[maxi][minj]+sm[mini][minj];
if(k==1)
{
minresult[k][mini][maxi][minj][maxj]=sum*sum;
return minresult[k][mini][maxi][minj][maxj];
}
if(minresult[k][mini][maxi][minj][maxj]!=INF)
return minresult[k][mini][maxi][minj][maxj];
for(int i=mini+1;i<maxi;i++)
{
s=sm[i][maxj]-sm[mini][maxj]-sm[i][minj]+sm[mini][minj];
res=getMinr(mini,i,minj,maxj,k-1)+(sum-s)*(sum-s);
if(res<minr) minr=res;
res=getMinr(i,maxi,minj,maxj,k-1)+s*s;
if(res<minr) minr=res;
}
for(int i=minj+1;i<maxj;i++)
{
s=sm[maxi][i]-sm[mini][i]-sm[maxi][minj]+sm[mini][minj];
res=getMinr(mini,maxi,minj,i,k-1)+(sum-s)*(sum-s);
if(res<minr) minr=res;
res=getMinr(mini,maxi,i,maxj,k-1)+s*s;
if(res<minr) minr=res;
}
minresult[k][mini][maxi][minj][maxj]=minr;
return minr;
}
int main()
{
double result;
while(cin>>n)
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
scanf("%d",&chess[i][j]);
for(int i=1;i<8;i++)
sm[0][i]=0,sm[i][0]=0;
for(int i=1;i<=8;i++)
{
int temp=0;
for(int j=1;j<=8;j++)
{
temp+=chess[i-1][j-1];
sm[i][j]=sm[i-1][j]+temp;
}
}
for(int k=1;k<=n;k++)
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
for(int l=0;l<9;l++)
for(int m=0;m<9;m++)
minresult[k][i][j][l][m]=INF;
int m=getMinr(0,8,0,8,n);
result=m*1.0/n-sm[8][8]*sm[8][8]*1.0/(n*n);
printf("%.3lf\n",sqrt(result));
}
}
经过以上的分析之后,终于明白必须得将递归表达式转化成自底向上的DP去解决...
#include<iostream>
#include<cmath>
using namespace std;
int chess[8][8],n;
int minresult[15][9][9][9][9];//保存结果
int sm[9][9];//保存从0,0-i-1,j-1的矩形块的数据和
const int INF=10000000;
int getMinr(int k,int mini,int minj,int maxi,int maxj)
{
int res,s,minr=INF,sum;
sum=sm[maxi][maxj]-sm[mini][maxj]-sm[maxi][minj]+sm[mini][minj];
for(int i=mini+1;i<maxi;i++)
{
s=sm[i][maxj]-sm[mini][maxj]-sm[i][minj]+sm[mini][minj];
res=minresult[k][mini][minj][i][maxj]+(sum-s)*(sum-s);
if(res<minr) minr=res;
res=minresult[k][i][minj][maxi][maxj]+s*s;
if(res<minr) minr=res;
}
for(int i=minj+1;i<maxj;i++)
{
s=sm[maxi][i]-sm[mini][i]-sm[maxi][minj]+sm[mini][minj];
res=minresult[k][mini][minj][maxi][i]+(sum-s)*(sum-s);
if(res<minr) minr=res;
res=minresult[k][mini][i][maxi][maxj]+s*s;
if(res<minr) minr=res;
}
return minr;
}
int main()
{
double result;
while(cin>>n)
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
scanf("%d",&chess[i][j]);
for(int i=1;i<8;i++)
sm[0][i]=0,sm[i][0]=0;
for(int i=1;i<=8;i++)
{
int temp=0;
for(int j=1;j<=8;j++)
{
temp+=chess[i-1][j-1];
sm[i][j]=sm[i-1][j]+temp;
}
}
for(int k=1;k<=n;k++)
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
for(int l=0;l<9;l++)
for(int m=0;m<9;m++)
minresult[k][i][j][l][m]=INF;
int m=getMinr(0,8,0,8,n);
for(int mini=0;mini<9;mini++) //行从第mini行开始
for(int minj=0;minj<9;minj++)//列从第minj列开始
for(int maxi=mini+1;maxi<9;maxi++) //按第maxi行分割
for(int maxj=minj+1;maxj<9;maxj++)//按第maxj列分割 这样组成一块小矩形区域
{
int temp=sm[maxi][maxj]-sm[mini][maxj]-sm[maxi][minj]+sm[mini][minj];
minresult[1][mini][minj][maxi][maxj]=temp*temp;
}
for(int k=2;k<=n;k++)
for(int mini=0;mini<9;mini++) //行从第mini行开始
for(int minj=0;minj<9;minj++)//列从第minj列开始
for(int maxi=mini+1;maxi<9;maxi++) //按第maxi行分割
for(int maxj=minj+1;maxj<9;maxj++)//按第maxj列分割 这样组成一块小矩形区域
minresult[k][mini][minj][maxi][maxj]=getMinr(k-1,mini,minj,maxi,maxj);
m=minresult[n][0][0][8][8];
result=m*1.0/n-sm[8][8]*sm[8][8]*1.0/(n*n);
printf("%.3lf\n",sqrt(result));
}
}
这次收获颇大....DP的状态刚好与递归的参数一致！
最后说下. 这天下午我让我朋友参谋上面的那段递归记忆化搜索的代码。。发现其实可以过的。。而修改只要在一个地方...
初始化 memset(minresult,0,sizeof(minresult));
在递归的时候判断
if(minresult[k][mini][maxi][minj][maxj])
return minresult[k][mini][maxi][minj][maxj];
就可以过了 0ms。。纳闷中。。。
初始化最大的时候可能会遇到这种情况..minresult还是会等于INF 而会一直递归..
最后的收获就是 最好在递归的时候用最简单的状态来判断是否被搜索过了！！！！
posted on 2009-04-01 12:15
米游 阅读(885)
评论(4) 编辑 收藏 引用 所属分类:
ACM