題目中文不解釋了。
剛開始做這題，我想到的就是遞歸.因為子問題與大問題完全一樣..
于是連公式都未化簡，寫了個遞歸程序。測試的時候發現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
米游 閱讀(933)
評論(4) 編輯 收藏 引用 所屬分類:
ACM