洛谷 P1436 棋盘分割 题解【搜索】/【区间DP】【前缀和】

作者: wjyyy 分类: DP,前缀和,区间DP,搜索,解题报告 发布时间: 2018-07-11 15:39

点击量:5

 

   为什么正解是DP。。。

 

题目描述

将一个8×8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的两部分中的任意一块继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的平方和最小。

请编程对给出的棋盘及n,求出平方和的最小值。

输入输出格式

输入格式:

第1行为一个整数n(1<n<15)。

 

第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

 

输出格式:

仅一个数,为平方和。

 

输入输出样例

输入样例#1:
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
输出样例#1:
1460

题解:

   题目一看上去:两边只选一边分,二叉树?但是可以沿着任何一条边分,状态太多不好处理。于是试着搜索,权值和用二维前缀和优化。

 

   因为棋盘固定为8×8,所以对于初始状态,枚举1~7行(作为上半边最下一行),再枚举分上半边还是下半边,如果选择一半,就计算另一半权值和的平方,加入sum,dfs另一半。还要枚举1~7列,dfs枚举左半边和右半边。

 

   由此可以推到一般情况,dfs带入左上角坐标\((lx,ly)\)、右下角坐标\((rx,ry)\)确定一个矩形。枚举\([lx,ry)\)行,与上面做相同的操作,各计算两边的权值和平方(一边dfs出来后算另一边时记得减掉),另一边带入dfs。

 

   当dfs进行到第n次时,就终止过程(要在函数开始时判断,不能执行第n次)。此时计算当前矩形权值和的平方,加入sum,与答案进行比较取较小值。

 

剪枝:

    最优解剪枝:这个搜索只用这一个剪枝就可以把代码从50分优化到100分,当目前sum大于已经计算出来的minn时,直接返回。


DP版题解:

   看作一个区间DP,因为这种分割形式类似一维,所以像区间DP一样枚举断点。每一层(被切割了i次)状态由i-1转移,枚举横切纵切,并取最小值。除第0层外,初始化为inf。

Code dfs:

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
int b[10][10];
int minn=0x3fffffff;
int cal(int lx,int ly,int rx,int ry)//计算前缀和
{
    return b[rx][ry]-b[lx-1][ry]-b[rx][ly-1]+b[lx-1][ly-1];
}
int sum=0,n;
void dfs(int k,int lx,int ly,int rx,int ry)
{
    if(sum>minn)
        return;
    if(k+1==n)
    {
        int now=cal(lx,ly,rx,ry);
        now*=now;//最后加上这一矩阵的平方
        minn=min(sum+now,minn);
        return;
    }
    //枚举从第i行切
    for(int i=lx;i<rx;i++)
    {
        int half=cal(i+1,ly,rx,ry)*cal(i+1,ly,rx,ry);
        sum+=half;
        dfs(k+1,lx,ly,i,ry);
        sum-=half;
        half=cal(lx,ly,i,ry)*cal(lx,ly,i,ry);
        sum+=half;
        dfs(k+1,i+1,ly,rx,ry);
        sum-=half;
    }
    //枚举从第i列切
    for(int i=ly;i<ry;i++)
    {
        int half=cal(lx,i+1,rx,ry)*cal(lx,i+1,rx,ry);
        sum+=half;
        dfs(k+1,lx,ly,rx,i);
        sum-=half;
        half=cal(lx,ly,rx,i)*cal(lx,ly,rx,i);
        sum+=half;
        dfs(k+1,lx,i+1,rx,ry);
        sum-=half;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
        {
            scanf("%d",&b[i][j]);
            b[i][j]+=b[i-1][j]+b[i][j-1];
            b[i][j]-=b[i-1][j-1];
        }
    sum=0;
    dfs(0,1,1,8,8);//初态
    printf("%d\n",minn);
    return 0;
}

 

Code DP:

#include<cstdio>
#include<cstring>

int f[18][9][9][9][9];
int b[9][9];
int min(int x,int y)
{
    return x<y?x:y;
}
int cal(int lx,int ly,int rx,int ry)
{
    return b[rx][ry]-b[lx-1][ry]-b[rx][ly-1]+b[lx-1][ly-1];
}
int main()
{
    memset(f,0x3f,sizeof(f));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
        {
            scanf("%d",&b[i][j]);
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    for(int lx=1;lx<=8;lx++)//初始化
        for(int ly=1;ly<=8;ly++)
            for(int rx=lx;rx<=8;rx++)
                for(int ry=ly;ry<=8;ry++)
                    f[0][lx][ly][rx][ry]=cal(lx,ly,rx,ry)*cal(lx,ly,rx,ry);

    for(int k=1;k<n;k++)
        for(int lx=1;lx<=8;lx++)
            for(int ly=1;ly<=8;ly++)
                for(int rx=lx;rx<=8;rx++)
                    for(int ry=ly;ry<=8;ry++)
                    {
                        for(int i=lx;i<rx;i++)
                            f[k][lx][ly][rx][ry]=min(f[k][lx][ly][rx][ry],min(f[k-1][lx][ly][i][ry]+cal(i+1,ly,rx,ry)*cal(i+1,ly,rx,ry),f[k-1][i+1][ly][rx][ry]+cal(lx,ly,i,ry)*cal(lx,ly,i,ry)));
                        for(int i=ly;i<ry;i++)
                            f[k][lx][ly][rx][ry]=min(f[k][lx][ly][rx][ry],min(f[k-1][lx][ly][rx][i]+cal(lx,i+1,rx,ry)*cal(lx,i+1,rx,ry),f[k-1][lx][i+1][rx][ry]+cal(lx,ly,rx,i)*cal(lx,ly,rx,i)));
                    }
    printf("%d\n",f[n-1][1][1][8][8]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */