解題區/解題區 - UVa

UVa 1169 - Robotruck

contents

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

Problem

在一個二維平面中，灑落 N 個垃圾，機器人從原點 (0, 0) 依序要蒐集垃圾，機器人一次承載 W 重量的垃圾，隨時可以返回原點將垃圾放下。

請問依序收集垃圾的最少花費為何？

Sample Input

1
2
3
4
5
6
7
8
1
10
4
1 2 3
1 0 3
3 1 4
3 1 4

Sample Output

1
14

Solution

一開始得到方程式 dp[i] = min(dp[j-1] + cost[j, i] + dist[j] + dist[i]) 必須滿足 w[j, i] <= C，其中 j <= i。

其中 dp[i] 表示依序收集前 i 個垃圾的最小花費，cost[j, i] 表示走訪編號 j 到 i 垃圾位置的花費，補上原點到編號 j，並且收集完從 i 回到原點。

這樣的方程式轉換需要 N^2 時間，化簡一下式子

1
2
3
dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]

會發現 i, j 獨立，也滿足垃圾重量累計遞增，因此盡可能保留 dp[j-1] - cost[j] + dist[j] 小的結果，並且重量不超過限制，當重量超過限制時，該組答案在隨後保證再也不會用到，直接捨棄之。

核心就是單調隊列的思路。

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
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int x[MAXN], y[MAXN], w[MAXN];
int cost[MAXN], dist[MAXN];
int dp[MAXN];
int f(int j) {
    return dp[j-1] - cost[j] + dist[j];
}
int main() {
    int testcase, C, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &C, &N);
        w[0] = 0, cost[0] = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%d %d %d", &x[i], &y[i], &w[i]);
            cost[i] = cost[i-1] + abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
            dist[i] = abs(x[i]) + abs(y[i]);
            w[i] += w[i-1];
        }
        // dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
        // dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
        // dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]
        deque<int> Q;
        Q.push_back(0);
        for (int i = 1; i <= N; i++) {
            while (!Q.empty() && w[i] - w[Q.front()] > C)
                Q.pop_front();
            dp[i] = f(Q.front() + 1) + cost[i] + dist[i];
            while (!Q.empty() && f(Q.back() + 1) >= f(i + 1))
                Q.pop_back();
            Q.push_back(i);
        }
        printf("%d\n", dp[N]);
        if (testcase)	puts("");
    }
    return 0;
}