P7179 [COCI2014-2015#4]STANOVI TJ

· · 题解

题目链接

记忆化搜索，其实思路不太难吧，但是优化比较难想，建议评蓝。

题意简述：

有一个 m\times n 的方格矩阵，把这个矩阵分为若干部分，且要求每一个矩阵都要与边界相邻。令 k 为标准面积，不满意度为{所有矩阵面积减去 k 的平方}之和。求最小的不满意度。

搜索

题库里有道题叫生日快乐（这道题是蓝的，但是难度严重虚高，个人觉得最多是绿），其实思路相仿，不过这题要难一些。

我们假设拿到了一个已知所有信息、且满足四周有边界的矩阵，我们要对它进行搜索。

首先我们要解决传参问题：什么算已知条件，而且如何判断这个矩阵是不是满足条件呢？

首先长和宽是有必要的。而且因为这道题要求每一个矩阵都要挨着边界，所以我们需要知道它四面挨着边界的情况。

dfs 函数中传 6 个参数：

解决完了 dfs 函数的传参问题，那怎么搜索呢？

我们先来分析出口。

由于题目要求，只要已知一个矩阵四面都没挨着边界，就直接返回一个极大值。

对于一个满足条件且已知的矩阵，有两种思路：

  1. 直接把它作为一个最终划分的矩阵；

  2. 把它继续分成更小的矩阵。

第一种思路很好解决，直接按照长、宽求就行了。

关键是第二种。

为了方便大家理解，我随便画了一个矩阵举例说明：

（Excel 真好用啊，蓝色为边界的外面那一圈）

对于这个矩阵，我们又有两种划分的方法：

  1. 横着切；

（红色的地方就是能切的地方。）

  1. 竖着切。

那我们只需要分两种情况，分别枚举切割的地方，寻找最小值就可以了。（比如说，枚举上面/左边那个矩阵的长/宽）

最后再看一下哪种情况会更好。

注意一个细节：横着切需满足 x>1，竖着切需满足 y>1。

核心代码大概长这样：

if(!(up||down||left||right)) return inf; //不沿海 
ll ans1=pow(x*y-k,2);
if(x==1&&y==1) return ans1;
ll ans2=inf;
bool u1,u2,d1,d2,l1,l2,r1,r2;
//横着分开
u1=up,u2=0,d1=0,d2=down,l1=l2=left,r1=r2=right;
if(x>1){
    for(int i=1;i<x;i++){
        int t=dfs(i,y,u1,d1,l1,r1)+dfs(x-i,y,u2,d2,l2,r2);
        ans2=min(ans2,t);
    }
}
//竖着分开 
u1=u2=up,d1=d2=down,l1=left,l2=0,r1=0,r2=right;
if(y>1){
    for(int i=1;i<y;i++){
    int t=dfs(x,i,u1,d1,l1,r1)+dfs(x,y-i,u2,d2,l2,r2);
        ans2=min(ans2,t);
    }
}
return min(ans1,ans2);

记忆化

开一个六维的数组 dp，每一维都对应一个传的参数，把 dfs 的值存在里面即可。

这个时候有人就会说了：可是不一样的矩阵可能六个参数都一样，那这个如何判断？

答案是不需要判断。虽然的确这种情况是存在的，但是，如果六个参数都一样，算出来的结果肯定也一样，这不会影响结果，还会减小运行的时间。

剪枝

观察一下上面的图，不难发现，有一些情况是不能做横着或者竖着的分割的，比如说这种：

这个东西就不能竖着切，因为如果竖着切了，左边的那个矩阵就不挨着边界了。

那我们可以写出矩阵要横着切和竖着切的条件：

为什么呢？以横着切举例：

现在四面是否挨着边界不知道。

如果要求成功，就必须满足下列至少一个条件：

  1. 上面和下面都挨着边界。

  2. 左边挨着边界，或者右边挨着边界。

你们自己去想一想，竖着也类似。

很好想，要是一个矩阵的面积小于 k，就不继续切了，直接返回。

zszz 矩阵是可以转的对吧？

拿到一个矩阵之后，我们可以尝试把它转一下：可以向左旋转 0^{\circ},90^{\circ},180^{\circ},270^{\circ}，每一种旋转都可以查看是否已求出结果，如果有，直接返回。

代码比较简单，但是思考的过程比较绕：

if(dp[x][y][up][down][left][right]!=-1) return dp[x][y][up][down][left][right]; //正常 
if(dp[x][y][down][up][right][left]!=-1) return dp[x][y][down][up][right][left]; //倒立 
if(dp[y][x][left][right][down][up]!=-1) return dp[y][x][left][right][down][up]; //往左转 
if(dp[y][x][right][left][up][down]!=-1) return dp[y][x][right][left][up][down]; //往右转

剪枝就这三个。虽然不多，但足以通过这道题。

最后再卡一下常。

Code

#include<cstdio>
#include<cmath>
#include<cstring>
#define min(a,b) (a)<(b)?(a):(b);
#define ll long long
const int maxn=305;
const ll inf=(ll)2e9;
int n,m,k;
ll dp[maxn][maxn][2][2][2][2];
ll dfs(int x,int y,bool up,bool down,bool left,bool right){ //bool 类型记录是否四个方向沿海 
    if(dp[x][y][up][down][left][right]!=-1) return dp[x][y][up][down][left][right]; //正常 
    if(dp[x][y][down][up][right][left]!=-1) return dp[x][y][down][up][right][left]; //倒立 
    if(dp[y][x][left][right][down][up]!=-1) return dp[y][x][left][right][down][up]; //往左转 
    if(dp[y][x][right][left][up][down]!=-1) return dp[y][x][right][left][up][down]; //往右转 
    if(!(up||down||left||right)) return inf; //不沿海 
    ll ans1=pow(x*y-k,2);
    if(x==1&&y==1||x*y<k) return dp[x][y][up][down][left][right]=ans1;
    ll ans2=inf;
    bool u1,u2,d1,d2,l1,l2,r1,r2;
    //横着分开 
    if(x>1&&(up&&down||left||right)){
        u1=up,u2=0,d1=0,d2=down,l1=l2=left,r1=r2=right;
        for(register int i=1;i<x;i++){
            int t=dfs(i,y,u1,d1,l1,r1)+dfs(x-i,y,u2,d2,l2,r2);
            ans2=min(ans2,t);
        }
    }
    //竖着分开 
    if(y>1&&(left&&right||up||down)){
        u1=u2=up,d1=d2=down,l1=left,l2=0,r1=0,r2=right;
        for(register int i=1;i<y;i++){
            int t=dfs(x,i,u1,d1,l1,r1)+dfs(x,y-i,u2,d2,l2,r2);
            ans2=min(ans2,t);
        }
    }
    return dp[x][y][up][down][left][right]=min(ans1,ans2);
}
int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d %d %d",&m,&n,&k);
    printf("%lld",dfs(m,n,1,1,1,1)); 
    return 0;
}