contents
Problem
在一個二維平面中，灑落 N 個垃圾，機器人從原點 (0, 0) 依序要蒐集垃圾，機器人一次承載 W 重量的垃圾，隨時可以返回原點將垃圾放下。
請問依序收集垃圾的最少花費為何？
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
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]; } 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("%dn", dp[N]); if (testcase) puts(""); } return 0; }
|
近期评论