Cake slicing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 149 Accepted Submission(s): 86Problem DescriptionA 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.
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
Accepted Code:
1 /*************************************************************************
2 > File Name: 2513.cpp
3 > Author: Stomach_ache
4 > Mail: sudaweitong@gmail.com
5 > Created Time: 2014年07月10日 星期四 18时34分23秒
6 > Propose:
7 ************************************************************************/
8
9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17
18 #define min(x, y) ((x) < (y) ? (x) : (y))
19
20 int n, m, cherry;
21 int dp[22][22][22][22];
22 int a[22][22], sum[22][22];
23
24 int DP(int sx, int ex, int sy, int ey) {
25 if (dp[sx][ex][sy][ey] != -1) return dp[sx][ex][sy][ey];
26 int cnt = 0;
27 for (int i = sx; i <= ex; i++) for (int j = sy; j <= ey; j++)
28 if (a[i][j]) cnt++;
29 if (cnt == 1) return dp[sx][ex][sy][ey] = 0;
30
31 int ans = 0x3f3f3f3f;
32 for (int i = sx; i < ex; i++) {
33 int tmp = sum[i][ey] - sum[i][sy-1] - sum[sx-1][ey] + sum[sx-1][sy-1];
34 if (tmp) {
35 ans = min(ans, DP(sx, i, sy, ey)+DP(i+1, ex, sy, ey)+ey-sy+1);
36 }
37 }
38 for (int i = sy; i < ey; i++) {
39 int tmp = sum[ex][i] - sum[ex][sy-1] - sum[sx-1][i] + sum[sx-1][sy-1];
40 if (tmp) {
41 ans = min(ans, DP(sx, ex, sy, i)+DP(sx, ex, i+1, ey)+ex-sx+1);
42 }
43 }
44 return dp[sx][ex][sy][ey] = ans;
45 }
46
47 int main(void) {
48 int c = 1;
49 while(~scanf("%d %d %d", &n, &m, &cherry)) {
50 memset(a, 0, sizeof(a));
51 for (int i = 0; i < cherry; i++) {
52 int x, y;
53 scanf("%d %d", &x, &y);
54 a[x][y] = 1;
55 }
56 memset(sum, 0, sizeof(sum));
57 for (int i = 1; i <= n; i++) {
58 for (int j = 1; j <= m; j++) {
59 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
60 if (a[i][j]) sum[i][j]++;
61 }
62 }
63 memset(dp, -1, sizeof(dp));
64 DP(1, n, 1, m);
65 printf("Case %d: %d\n", c++, dp[1][n][1][m]);
66 }
67
68 return 0;
69 }
原文：http://www.cnblogs.com/Stomach-ache/p/3836617.html