随笔-38  评论-23  文章-0  trackbacks-0


题目中文不解释了。
刚开始做这题,我想到的就是递归.因为子问题与大问题完全一样..
于是连公式都未化简,写了个递归程序。测试的时候发现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 米游 阅读(868) 评论(4)  编辑 收藏 引用 所属分类: ACM

评论:
# re: pku 1191 棋盘分割 (DP)(三) 2009-08-22 11:09 | sakuratest
真的受益匪浅。代码从高复杂度向低复杂度的思路条理非常清晰,代码格式也很好,注释虽然不多,但很清晰。很好的学习文!!!  回复  更多评论
  
# re: pku 1191 棋盘分割 (DP)(三)[未登录] 2009-08-22 13:13 | 米游
@sakuratest
这是以前写代码所没有注意到的一个好习惯>_< 不写注释。。现在的代码好多了。可惜我已经好久没有做ACM的题了  回复  更多评论
  
# re: pku 1191 棋盘分割 (DP)(三) 2009-09-09 08:14 | shizu
请问下,如果这题同时要你输出每个分割的数组坐标,即左上起始坐标和右下中止坐标,自下而上的方法似乎就有问题了吧~~请指教!!谢谢~  回复  更多评论
  
# re: pku 1191 棋盘分割 (DP)(三) 2009-09-12 11:22 | 米游
我觉得你完全可以在getMinr()这个函数中记录你想要的起始和终止坐标,因为分成K个区域.会从K-1个区域中得来..因此.你完全可以在getMinr()记录这个区域.因为其中计算res的时候本身就是一个区域值?
@shizu
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理