pku1191 棋盘分割 (动态规划)

题目：

题目是中文的，意思就不说了。。分析部分见《算法艺术与信息学竞赛》（刘汝佳）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;
}

很不明白的是为什么后者的时间比前者还要长。。。

阅读(3527) | 评论(1) | 转发(0) |

0

上一篇：(xmu H)Time Limit Exceed (直接模拟)

下一篇：pku3462 Lucky Light (简单题)