UVA 1169(dp + 단일 큐)
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[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
", solve());
if (t) printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.