2014
02-09

# 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.

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.

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

#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;

}

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