Cake slicing

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

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.
<center> </center>
One allowable slicing is as follows.
<center> </center>
For this way of slicing , the total length of the cutting edges is 2+4=6.
Another way of slicing is
<center> </center>
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
 

Source
ECJTU 2008 Autumn Contest
 

Recommend
lcy   |   We have carefully selected several similar problems for you:   2514  2510  2511  2512  2515 

                  emmmmm具体细节我在代码中阐述吧~~不然空讲好奇怪~QAQ


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int dp[30][30][30][30];//dp[a][b][c][d]表示把以（a，b）和（c，d）作为左上右下角的矩形切割成符合情况所需要的最小值
int m[30][30];//用来储存樱桃的位置；
int y,x,sum;
#define maxn 0x3f3f3f3f
int sol(int a,int b,int c,int d)//表示把（a,b）和(c,d)作为左上右下角的矩形切割的最小值；
{
    if(dp[a][b][c][d]==-1)//如果之前没有计算过，那就计算；
    {
        int cnt=0;
        for(int s=a;s<=c;s++)
        {
            for(int w=b;w<=d;w++)
            {
                if(m[s][w])
                {
                    cnt++;//用来检查有几个樱桃
                }
            }
        }
        if(cnt<=1)//小于2个就不用切割了；
        {
            dp[a][b][c][d]=0;
            return 0;
        }
        int minn=maxn;//不然就直接包里寻找断点
        for(int s=a;s<c;s++)//这是横着切
        {
            minn=min(minn,sol(a,b,s,d)+sol(s+1,b,c,d)+d-b+1);
        }
        for(int s=b;s<d;s++)//竖着切
        {
            minn=min(minn,sol(a,b,c,s)+sol(a,s+1,c,d)+c-a+1);
        }
        dp[a][b][c][d]=minn;
    }
    return dp[a][b][c][d];
}
void init()
{
    memset(m,0,sizeof(m));
    memset(dp,-1,sizeof(dp));//初始化为-1；
}
int main()
{
    int cas=1;
    while(cin>>y>>x>>sum)
    {
        init();
        for(int s=0;s<sum;s++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            m[a][b]=1;
        }
        int ans=sol(1,1,y,x);
        printf("Case %d: %d\n",cas++,ans);
    }
    return 0;
}