多校联合训练的常见问题回答（FAQ）
Cake slicing\Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 583 Accepted Submission(s): 305 ** Problem DescriptionA rectangular cake with a grid of mn 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 34 unit squares on its top, and there are three cherries on the top, as shown in the figure below. img One allowable slicing is as follows. img For this way of slicing , the total length of the cutting edges is 2+4=6. Another way of slicing is img 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. InputThe 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. OutputOutput an integer indicating the least total length of the cutting edges. Sample Input3 4 3 1 2 2 3 3 2 Sample OutputCase 1: 5 SourceECJTU 2008 Autumn Contest

【题意】

有一个n*m大小的蛋糕，上面有k个樱桃，现在我们需要把这个蛋糕切成k份，使每份蛋糕上有一个樱桃，问最小切割长度和。(切割一刀必须切到底)

我参考了网上的博客,思路如下:

这是一道区间Dp的题目;$dp[i][j][k][l]$表示以(i,j)为左上角,(k,l)为右下角的点,实际操作中因为初始化等问题,对于

image-20200620162927557
image-20200620162927557

因为判定樱桃数量的函数使用的是<=,所以实际上是判断的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int MAXN=0x3f3f3f3f;
int m[25][25];
int dp[25][25][25][25];

int y,x,sum;//y*x矩阵；sum个樱桃;

int Dp(int i,int j,int k,int l){//以i,j为左上角,k,l为右下角
    if(dp[i][j][k][l]!=-1){
        return dp[i][j][k][l];
    }//如果之前计算过了,直接返回;
    //统计区域里面的樱桃数量;
    int cherry=0;
    for(int a=i;a<=k;++a){
        for(int b=j;b<=l;++b){
            if(m[a][b]==1){
                cherry+=1;
            }
        }
    }
    //如果樱桃数量==1,那么不需要切割,返回0;
    if(cherry==1){
        dp[i][j][k][l]=0;
        return 0;
    }
    //如果是0,那么这是一个不应该取得解,返回INF;
    if(cherry==0){
        dp[i][j][k][l]=MAXN;
        return MAXN;
    }
    //否则需要切割;横着切或者纵着切;
    int minn=MAXN;
    //横着切:
    for(int a=i;a<k;++a){
        minn=min(minn,Dp(i,j,a,l)+Dp(a+1,j,k,l)+l-j+1);
    }
    //纵着切割:
    for(int b=j;b<l;++b){
        minn=min(minn,Dp(i,j,k,b)+Dp(i,b+1,k,l)+k-i+1);
    }
    dp[i][j][k][l]=minn;
    return dp[i][j][k][l];



}

void init(){
    memset(dp,-1,sizeof(dp));
    memset(m,0,sizeof(m));
}

int main() {
    int cnt=1;
    while(~scanf("%d%d%d",&y,&x,&sum)){
        init();
        for(int i=0;i<sum;++i){
            int p,q;
            scanf("%d%d",&p,&q);
            m[p][q]=1;
        }
        Dp(1,1,y,x);
        printf("Case %d: %d\n",cnt,dp[1][1][y][x]);
        cnt+=1;
    }
    return 0;
}