解題區/解題區 - UVa

UVa 1336 - Fixing the Great Wall

contents

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

Problem

有一台機器必須修復長城的所有位置，每一個位置的修復時間都是瞬間完成，但是移動必須耗時，而每一個位置的修復成本與修復時間呈現花費 c + d * t，求最少花費。

Sample Input

1
2
3
4
5
6
7
8
9
3 1 1000
1010 0 100
998 0 300
996 0 3
3 1 1000
1010 0 100
998 0 3
996 0 3
0 0 0

Sample Output

1
2
2084
1138

Solution

首先，可以藉由貪心得到，既然修復時間是瞬間，所經之處必然會修理完成。

因此狀態會呈現某一個區間已完成，並且停留在左端點或者是右端點，然而費用的計算則相當麻煩，因為計算某個區間而言，並不知道這區間花費的移動時間成本，只知道其最小花費。

反過來思考，利用潛熱的概念，預先支付往後所有未經過的位置所需要的花費，那麼就可以得到從左右端點彼此之間的移動時間 dt，將會增加未經過位置的所有 sumc，得到預支付花費 dt * sumc。

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
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 1024
#define INF 1000000005
struct Pos {
    int x, c, delta; // cost = c + t * delta
    bool operator<(const Pos &a) const {
        return x < a.x;
    }
} D[MAXN];
int sumD[MAXN];
double dp[MAXN][MAXN][2]; // [interval_length][l][stop interval left/right]
int main() {
    int N, X;
    double V;
    while (scanf("%d %lf %d", &N, &V, &X) == 3 && N) {
        for (int i = 1; i <= N; i++)
            scanf("%d %d %d", &D[i].x, &D[i].c, &D[i].delta);
        sort(D + 1, D + 1 + N);
        
        sumD[0] = 0;
        for (int i = 1; i <= N; i++)
            sumD[i] = sumD[i-1] + D[i].delta;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N + 1; j++) {
                dp[i][j][0] = dp[i][j][1] = INF;
            }
        }
        for (int i = 1; i <= N; i++) {
            double cost = sumD[N] * (fabs(X - D[i].x) / V) + D[i].c;
            dp[1][i][0] = dp[1][i][1] = cost;
        }
        
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j + i - 1 <= N; j++) {
                int l = j, r = j + i - 1;
                double fromL, fromR;
                fromL = fromR = INF;
                fromL = dp[i-1][l+1][0] + (sumD[l] + sumD[N] - sumD[r]) * ((D[l+1].x - D[l].x) / V) + D[l].c;
                fromR = dp[i-1][l+1][1] + (sumD[l] + sumD[N] - sumD[r]) * ((D[r].x - D[l].x) / V) + D[l].c;
                dp[i][l][0] = min(fromL, fromR);
                
                fromL = dp[i-1][l][0] + (sumD[l-1] + sumD[N] - sumD[r-1]) * ((D[r].x - D[l].x) / V) + D[r].c;
                fromR = dp[i-1][l][1] + (sumD[l-1] + sumD[N] - sumD[r-1]) * ((D[r].x - D[r-1].x) / V) + D[r].c;
                dp[i][l][1] = min(fromL, fromR);
            }
        }
        printf("%d\n", (int) min(dp[N][1][0], dp[N][1][1]));
    }
    return 0;
}