首页 > ACM题库 > HDU-杭电 > hdu 2513 Cake slicing-动态规划-[解题报告]C++
2014
02-09

hdu 2513 Cake slicing-动态规划-[解题报告]C++

Cake slicing

问题描述 :

A rectangular cake with a grid of m*n unit squares on its top needs to be sliced into pieces. Several cherries are scattered on the top of the cake with at most one cherry on a unit square. The slicing should follow the rules below:
1.  each piece is rectangular or square;
2.  each cutting edge is straight and along a grid line;
3.  each piece has only one cherry on it;
4.  each cut must split the cake you currently cut two separate parts

For example, assume that the cake has a grid of 3*4 unit squares on its top, and there are three cherries on the top, as shown in the figure below.


One allowable slicing is as follows.

For this way of slicing , the total length of the cutting edges is 2+4=6.
Another way of slicing is

In this case, the total length of the cutting edges is 3+2=5.

Give the shape of the cake and the scatter of the cherries , you are supposed to find
out the least total length of the cutting edges.

输入:

The input file contains multiple test cases. For each test case:
The first line contains three integers , n, m and k (1≤n, m≤20), where n*m is the size of the unit square with a cherry on it . The two integers show respectively the row number and the column number of the unit square in the grid .
All integers in each line should be separated by blanks.

输出:

The input file contains multiple test cases. For each test case:
The first line contains three integers , n, m and k (1≤n, m≤20), where n*m is the size of the unit square with a cherry on it . The two integers show respectively the row number and the column number of the unit square in the grid .
All integers in each line should be separated by blanks.

样例输入:

3 4 3
1 2
2 3
3 2

样例输出:

Case 1: 5

Cake slicing


Time
Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 70 Accepted Submission(s):
42

Problem Description

A rectangular cake with a grid of m*n
unit squares on its top needs to be sliced into pieces. Several
cherries are scattered on the top of the cake with at most one
cherry on a unit square. The slicing should follow the rules
below:
1. each piece is rectangular or square;
2. each cutting edge is straight and along a grid line;
3. each piece has only one cherry on it;
4. each cut must split the cake you currently cut two separate
parts

For example, assume that the cake has a grid of 3*4 unit squares on
its top, and there are three cherries on the top, as shown in the
figure below.

hdu2513


One allowable slicing is as follows.
hdu2513


For this way of slicing , the total length of the cutting edges is
2+4=6.
Another way of slicing is
hdu2513


In this case, the total length of the cutting edges is 3+2=5.

Give the shape of the cake and the scatter of the cherries , you
are supposed to find
out the least total length of the cutting edges.


Input

The input file contains multiple test
cases. For each test case:
The first line contains three integers , n, m and k (1≤n, m≤20),
where n*m is the size of the unit square with a cherry on it . The
two integers show respectively the row number and the column number
of the unit square in the grid .
All integers in each line should be separated by
blanks.


Output

Output an integer indicating the least
total length of the cutting edges.


Sample Input

3 4 3 1 2 2
3 3 2


Sample Output

Case 1:
5

 

这道题真是太可惜了,完全是因为题中有一个小地方没注意到,wa了十几次。

感觉像是区间动态规划的一个变形,对于给定的长方形,总是可以递归地转化更小的

长方形,具体来说,就是枚举长度不变的两个子矩形,和枚举宽度不变的两个子矩形。所以,用四个变量来记录状态,自底向上更新就可以得到解,要注意每一个子矩形中至少要含一个点,否则这种分割是不允许的。

这次最大的教训就是没有看清题意,就草率地开始思考算法,这个换习惯从今天起就要改掉。

 

 

代码


#include <iostream>


#include <cstdio>


#include <string.h>


using namespace std;


const int arr=20;


const int inf=1<<28 ;


int dp[arr+10][arr+10][arr+10][arr+10];


int num[arr+10][arr+10];


int sum[arr+10][arr+10];


int main()


{


    int n,m,k,ca=0;


    while(scanf(“%d%d%d”,&n,&m,&k)!=EOF)


    {


        memset(num,0,sizeof(num));


        memset(sum,0,sizeof(sum));


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


        {


            int x,y ;


            scanf(“%d%d”,&x,&y);


            num[x][y]=1;


        }


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


        {


            for(int j=1;j<=m;j++)


            {


                  sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+num[i][j];


            }


        }


        for(int w=1;w<=n;w++)


        {


            for(int h=1;h<=m;h++)


            {


                for(int i=1;i+w-1<=n;i++)


                {


                    int ix=w+i-1;


                    for(int j=1;j+h-1<=m;j++)


                    {


                        int jy=h+j-1;


                        if(i==ix&&j==jy)


                            dp[w][h][i][j]=0;


                        else{


                            int s=sum[ix][jy]-sum[i-1][jy]-sum[ix][j-1]+sum[i-1][j-1];


                            if(s==1){dp[w][h][i][j]=0;continue;}


                            if (s==0){dp[w][h][i][j] =inf;continue ;}


                            if(i==ix||j==jy)


                            {

 


                                if(s<=1)


                                    dp[w][h][i][j]=0;


                                else


                                    dp[w][h][i][j]=s-1;


                            }


                            else{


                                dp[w][h][i][j] =inf;


                                for(int t=i;t<ix;t++)


                                {


                                    s=dp[t-i+1][h][i][j]+dp[w-t+i-1][h][t+1][j]+h;


                                    if(dp[w][h][i][j]>s)


                                        dp[w][h][i][j]=s ;


                                }


                                for(int t=j;t<jy;t++)


                                {


                                    s=dp[w][t-j+1][i][j]+dp[w][h-t+j-1][i][t+1]+w;


                                    if(dp[w][h][i][j]>s)


                                        dp[w][h][i][j]=s;


                                }


                            }


                        }


                    }


                }


            }


        }


        printf(“Case %d: %d\n”,++ca,dp[n][m][1][1]);


    }

 


    return 0;


}

 

 





解题转自:http://blog.sina.com.cn/s/blog_803d08c00100xu95.html


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。