解題區/解題區 - UVa

UVa 1629 - Cake slicing

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

切割長方形蛋糕，使得每一塊上恰好有一個莓果，每一次切割的花費即線長，求最小花費。

Sample Input

1
2
3
4
3 4 3 
1 2 
2 3 
3 2

Sample Output

1
Case 1: 5

Solution

利用 DP 精神，考慮每一個地方都去切割，定義 dp[x][y][w][h] 為左上角座標 (x, y)，其長寬 (w, h) 的長方形蛋糕的最小花費。

沒有辦法對於連續空白之間只取一次切割，如果只切一次縱切的，切著左右兩側的橫切個數將會影響很大，所以每個位置都要嘗試。

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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
int N, M, K;
int g[32][32], sum[32][32];
int dp[32][32][32][32], used[32][32][32][32], testcase = 0;
int getArea(int x, int y, int w, int h) {
    return sum[x + w-1][y + h-1] - sum[x-1][y + h-1] - sum[x + w-1][y-1] + sum[x-1][y-1];
}
int dfs(int x, int y, int w, int h) {
    if (used[x][y][w][h] == testcase)
        return dp[x][y][w][h];
    if (getArea(x, y, w, h) < 2)
        return 0;
    used[x][y][w][h] = testcase;
    int &ret = dp[x][y][w][h];
    ret = 0x3f3f3f3f;
    for (int i = 1; i < w; i++) {
        if (getArea(x, y, i, h) > 0 && getArea(x+i, y, w-i, h) > 0)
            ret = min(ret, dfs(x, y, i, h) + dfs(x+i, y, w-i, h) + h);
    }
    for (int i = 1; i < h; i++) {
        if (getArea(x, y, w, i) > 0 && getArea(x, y+i, w, h-i) > 0)
            ret = min(ret, dfs(x, y, w, i) + dfs(x, y+i, w, h-i) + w);
    }
    return ret;
}
int main() {
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        memset(g, 0, sizeof(g));
        memset(sum, 0, sizeof(sum));
        int x, y;
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &x, &y);
            g[x][y]++;
        }
        for (int i = 1; i <= N; i++) {
            int x = 0;
            for (int j = 1; j <= M; j++) {
                x += g[i][j];
                sum[i][j] = sum[i-1][j] + x;
            }
        }
        testcase++;
        printf("Case %d: %d\n", testcase, dfs(1, 1, N, M));
    }
    return 0;
}