Chinaunix首页 | 论坛 | 博客
  • 博客访问: 452050
  • 博文数量: 98
  • 博客积分: 6011
  • 博客等级: 准将
  • 技术积分: 1030
  • 用 户 组: 普通用户
  • 注册时间: 2006-11-23 13:19
文章分类

全部博文(98)

文章存档

2011年(2)

2009年(2)

2008年(31)

2007年(35)

2006年(28)

我的朋友

分类:

2008-05-01 11:13:24

题目:
题目是中文的,意思就不说了。。分析部分见《算法艺术与信息学竞赛》(刘汝佳)116面。。。。大致如下:
1,先化简均方差公式,可以看出,只需要让每个分割后的矩形的总分的平方和尽量小,即可使均方差最小。
2,考虑左上角坐标为(x1,y1),右下角坐标为(x2,y2)的棋盘,设它的总和为s[x1,y1,x2,y2]切割k次以后得到k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2],则它可以沿着横线切,也可以沿着竖线切,然后选一块继续切(递归)。。
3,由1,2部可以得到状态转移方程:
d[k,x1,y1,x2,y2]=min{
min{d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]^2,d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]^2},
min{d[k-1,x1,y1,x2,b]+s[x1,b+1,x2,y2]^2,d[k-1,x1,b+1,x2,y2]+s[x1,y1,x2,b]^2}}
其中:(x1<=a
初始值,对于k==0,d[k,x1,y1,x2,y2]=s[x1,y1,x2,y2]^2;
我的代码(记忆化搜索):
 

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int sum[9][9];
int d[15][9][9][9][9];

int SUM(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}

int min(int a,int b)
{ return a>b?b:a; }

int fun(int k,int x1,int y1,int x2,int y2)
{
    int t,a,b,c,e,MIN=10000000;
    if(d[k][x1][y1][x2][y2]!=-1)
        return d[k][x1][y1][x2][y2];
    if(k==0)
    {
        t=SUM(x1,y1,x2,y2);
        d[k][x1][y1][x2][y2]=t*t;
        return t*t;
    }
    for(a=x1;a<x2;a++)
    {
        c=SUM(a+1,y1,x2,y2);
        e=SUM(x1,y1,a,y2);
        t=min(fun(k-1,x1,y1,a,y2)+c*c,fun(k-1,a+1,y1,x2,y2)+e*e);
        if(MIN>t) MIN=t;
    }
    for(b=y1;b<y2;b++)
    {
        c=SUM(x1,b+1,x2,y2);
        e=SUM(x1,y1,x2,b);
        t=min(fun(k-1,x1,y1,x2,b)+c*c,fun(k-1,x1,b+1,x2,y2)+e*e);
        if(MIN>t) MIN=t;
    }
    d[k][x1][y1][x2][y2]=MIN;
    return MIN;
}
int main()
{
    int n,i,j,s,value;
    double b;
    while(cin>>n)
    {
        for(i=0;i<=8;i++){sum[0][i]=0;sum[i][0]=0;}
        for(i=1;i<=8;i++)
            for(j=1,s=0;j<=8;j++)
            {
                cin>>value;s+=value;
                sum[i][j]=sum[i-1][j]+s;
            }
        memset(d,-1,sizeof(d));
        s=sum[8][8]*sum[8][8];
        value=fun(n-1,1,1,8,8);
        value*=n;value-=s;
        b=double(value)/double(n*n);
        cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(b)<<endl;
    }
    return 0;
}

但昨天晚上写的时候,给MIN赋初值是写成MIN=0x7fffffff,当n<=3的时候,没问题,贡献了五六次WA后,才发现n再大点,就会出现错误,但花了几个小时仍是没有找出错误,后来去掉递归,写成递推的形式,一步步调试,才找出错误。。原来很简单的道理,MIN已经是最大的int,它还要加上一些数,就溢出了,改成MIN=10000000后,AC...

下面是递推版本的DP:

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int sum[9][9];
int f[15][9][9][9][9];

int SUM(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}

int min(int a,int b)
{ return a>b?b:a; }

int fun(int k)
{
    int t,a,b,c,e,d,MIN,i,j,m,n;
    for(i=1;i<=8;i++)
        for(j=1;j<=8;j++)
            for(m=1;m<=8;m++)
                for(n=1;n<=8;n++)
                {
                    t=SUM(i,j,m,n);
                    f[0][i][j][m][n]=t*t;
                }
    for(a=1;a<=k;a++)
        for(i=1;i<=8;i++)
            for(j=1;j<=8;j++)
                for(m=1;m<=8;m++)
                    for(n=1;n<=8;n++)
                    {
                        MIN=10000000;
                        if((m-i+1)*(n-j+1)<a+1) {f[a][i][j][m][n]=MIN;continue;}
                        for(d=i;d<m;d++)
                        {
                            c=SUM(d+1,j,m,n);
                            e=SUM(i,j,d,n);
                            t=min(f[a-1][i][j][d][n]+c*c,f[a-1][d+1][j][m][n]+e*e);
                            if(MIN>t) MIN=t;
                        }
                        for(b=j;b<n;b++)
                        {
                            c=SUM(i,b+1,m,n);
                            e=SUM(i,j,m,b);
                            t=min(f[a-1][i][j][m][b]+c*c,f[a-1][i][b+1][m][n]+e*e);
                            if(MIN>t) MIN=t;
                        }
                        f[a][i][j][m][n]=MIN;
                    }
    return f[k][1][1][8][8];
}
int main()
{
    int n,i,j,s,value;
    double b;
    while(cin>>n)
    {
        for(i=0;i<=8;i++){sum[0][i]=0;sum[i][0]=0;}
        for(i=1;i<=8;i++)
            for(j=1,s=0;j<=8;j++)
            {
                cin>>value;s+=value;
                sum[i][j]=sum[i-1][j]+s;
            }
        s=sum[8][8]*sum[8][8];
        value=fun(n-1);
        value*=n;
        value-=s;
        b=double(value)/double(n*n);
        cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(b)<<endl;
    }
    return 0;
}

很不明白的是为什么后者的时间比前者还要长。。。
阅读(3522) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2008-07-27 21:29:42

你怎么写程序不加注释啊 可不是一个好习惯