首页 > 代码库 > Hdu 2513　区间DP

Hdu 2513　区间DP

2024-07-11 14:24:50   234人阅读

Cake slicing

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


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 31 22 33 2

 

Sample Output
Case 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 }

 


联系
我们