UVA 1169(dp + 單調隊列)

Problem C - Robotruck

Background

This problem is about a robotic truck that distributes mail packages to several locations in a factory. The robot sits at the end of a conveyer at the mail office and waits for packages to be loaded into its cargo area. The robot has a maximum load capacity, which means that it may have to perform several round trips to complete its task. Provided that the maximum capacity is not exceeded, the robot can stop the conveyer at any time and start a round trip distributing the already collected packages. The packages must be delivered in the incoming order.

The distance of a round trip is computed in a grid by measuring the number of robot moves from the mail office, at location (0,0), to the location of delivery of the first package, the number of moves between package delivery locations, until the last package, and then the number of moves from the last location back to the mail office. The robot moves a cell at a time either horizontally or vertically in the factory plant grid. For example, consider four packages, to be delivered at the locations (1,2), (1,0), (3,1), and (3,1). By dividing these packages into two round trips of two packages each, the number of moves in the first trip is 3+2+1=6, and 4+0+4=8 in the second trip. Notice that the two last packages are delivered at the same location and thus the number of moves between them is 0.

Problem

Given a sequence of packages, compute the minimum distance the robot must travel to deliver all packages.

Input

Input consists of multiple test cases the first line of the input contains the number of test cases. There is a blank line before each dataset. The input for each dataset consists of a line containing one positive integer C, not greater then 100, indicating the maximum capacity of the robot, a line containing one positive integer N, not greater than 100,000, which is the number of packages to be loaded from the conveyer. Next, there are Nlines containing, for each package, two non-negative integers to indicate its delivery location in the grid, and a positive integer to indicate its weight. The weight of the packages is always smaller than the robot’s maximum load capacity. The order of the input is the order of appearance in the conveyer.

Output

One line containing one integer representing the minimum number of moves the robot must travel to deliver all the packages. Print a blank line between datasets.

Sample Input

1

10

4

1 2 3

1 0 3

3 1 4

3 1 4

Sample Output

14

題意：有一個機器人，給定w和n，w代表機器人的最大負重，n代表坐标系上有n個垃圾，接下去n行代表垃圾的位置和重量，一開始機器人在原點，機器人隻能走橫豎，機器人可以拿多個垃圾，隻要不超過最大負重，然後放回垃圾桶，垃圾桶在原點，問機器人最少需要走的距離。

思路：n非常的大，沒什麼思路，看了劉汝佳的代碼，原來是加入了單調隊列去維護。dp[i]表示前i個垃圾需要的最少距離，然後先預處理出sumw[i]，前i個垃圾的重量之和，sumd[i]，路過前i個垃圾的距離之和，d[i]，i到原點的哈曼頓距離那麼對于j到i的垃圾，sumw = sumw[i] - sumw[j], sumd = sumd[i] - sumd[j]。由于對于dp[i]而言，最後機器人肯定是回到原點了，是以這樣一來可以推出狀态轉移方程為dp[i] = dp[j] + d[j + 1] + sumd + d[i] (if (sumw <= w)。如果單單這樣看的話，需要兩重for循環，複雜度是o(n^2)逾時。那麼把方程轉換一下變成: dp[i] = dp[j] + d[j + 1] - sumd[j + 1] + sumd[i] + d[i]; 設dp[j] + d[j + 1] - sumd[j + 1] = func(j);那麼對于每一個狀态dp[i] = func(j) + sumd[i] + d[i]; 要保證最小，隻要維護func(j)的最小值即可。這步就可以使用一個單調隊列來維護，使得複雜度降為o(n)。很巧妙的方法。

代碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <queue>
using namespace std;
const int N = 100005;

int t, w, n, sumw[N], sumd[N], dp[N];
struct Point {
	int x, y, w, d;
	Point() {x = 0; y = 0; w = 0; d = 0;}
} p[N], zero;;

int dis(Point a, Point b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

int func(int j) {
	return dp[j] - sumd[j + 1] + p[j + 1].d;
}

int solve() {
	deque<int> Q;
	Q.push_front(0);
	for (int i = 1; i <= n; i++) {
		while (!Q.empty() && sumw[i] - sumw[Q.front()] > w) {Q.pop_front();}
		dp[i] = func(Q.front()) + sumd[i] + p[i].d;
		while (!Q.empty() && func(i) <= func(Q.back())) {Q.pop_back();}
		Q.push_back(i);
	}
	return dp[n];
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &w, &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].w);
			sumw[i] = sumw[i - 1] + p[i].w;
			sumd[i] = sumd[i - 1] + dis(p[i], p[i - 1]);
			p[i].d = dis(p[i], zero);
		}
		printf("%d\n", solve());
		if (t) printf("\n");
	}
	return 0;
}