原题

LRJ入门经典-0903切蛋糕305

难度级别：B；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

如图所示有一个矩形蛋糕，上面划分成了n行m列的网格，一些网格内放着樱桃。现在要根据如下规则切蛋糕：

1.切开的每一块必须是矩形（包括正方形）

2.切蛋糕时必须沿着网格线，不能拐弯

3.切开的每一块蛋糕上有且仅有一个樱桃

下图是一种切割方法：

这种方法需要切割的边数为2+4=6

以下是另一种切割方法：

这种方法需要切割的边数为3+2=5

现在给定蛋糕的形状和上面樱桃的分布，要求求出切割边数最少的方案。

输入

第一行包含三个正整数n，m和k（1<=n,m<=20），k表示樱桃数量
以下k行每行包含两个正整数，表示每个樱桃所在的行和列

输出

输出最优方案的切割边数

输入示例

3 4 3
1 2
2 3
3 2

输出示例

分析

第一眼看到“（1<=n,m<=20）”就想到了DFS，但普通的DFS显而易见会超时，只能用记忆化搜索了。

dp[i1][j1][i2][j2]代表坐标为(i1,j1)的点与坐标为(i2,j2)的点围成的长方形蛋糕，将其切成蛋糕上有且仅有一个樱桃时的最小切割边数。（初值为-1）

代码

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,m,k,a[21][21],dp[21][21][21][21];

inline int check(int x1,int y1,int x2,int y2)

{

    int sum=0;

    for(int i=x1;i<=x2;i++)

        for(int j=y1;j<=y2;j++)

            if(a[i][j]) sum++;

    return sum;

}

inline int dfs(int x1,int y1,int x2,int y2)

{

    int &d=dp[x1][y1][x2][y2];

    if(d>-1) return d;

    int sum=check(x1,y1,x2,y2);

    if(sum==0) return d=1000000;

    if(sum==1) return d=0;

    int minn=1000000;

    for(int i=x1;i<x2;i++)

        minn=min(minn,dfs(x1,y1,i,y2)+dfs(i+1,y1,x2,y2)+(y2-y1+1));

    for(int i=y1;i<y2;i++)

        minn=min(minn,dfs(x1,y1,x2,i)+dfs(x1,i+1,x2,y2)+(x2-x1+1));

    return d=minn;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=k;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        a[x][y]=1;

    }

    memset(dp,-1,sizeof(dp));

    printf("%d",dfs(1,1,n,m));

}

巴特西

LRJ入门经典-0903切蛋糕305

原题

分析

代码

最新文章

热门文章