Problem Solving►UVa

UVa 10003 - Cutting Sticks

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

利用遞迴計算不同切割點時的花費，並記錄起來。
主要遞迴式: 

dp[l_idx][r_idx] = MIN(dp[l_idx][r_idx], solve(left, cut[i], l_idx, i - 1) + solve(cut[i], right, i + 1, r_idx) + len);

左半部分 + 右半部分 + 本次的cost

Code

UVa 10003UVa 10003 - Cutting Sticks
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
#include<cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 51

int cut[N], dp[N][N];
int solve(int left, int right, int l_idx, int r_idx);
int main()
{
    int len, n, i;
    while (scanf("%d", &len) && len)
    {
        scanf("%d", &n);
        for (i = 0; i < n; i++)
            scanf("%d", &cut[i]);

        for (i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                dp[i][j] = 1e9;

        printf("The minimum cutting is %d.\n", solve(0, len, 0, n - 1));
    }

    return 0;
}
int solve(int left, int right, int l_idx, int r_idx)
{
    /*
    left: 此段木棍左邊
    right: 此段木棍右邊
    l_idx: 欲使用之切割點的最左 index
    r_idx: 欲使用之切割點的最右 index
    */

    int len = right - left;
    if (l_idx == r_idx)//只有一點
        return len;
    else if (l_idx > r_idx)//沒有切割點
        return 0;
    else if (dp[l_idx][r_idx] != 1e9)//已計算過
        return dp[l_idx][r_idx];

    for (int i = l_idx; i <= r_idx; i++)
        dp[l_idx][r_idx] = MIN(dp[l_idx][r_idx], solve(left, cut[i], l_idx, i - 1) + solve(cut[i], right, i + 1, r_idx) + len);

    return dp[l_idx][r_idx];
}