算法：uva 1169 - Robotruck （单调队列优化dp）

算法：uva 1169 - Robotruck （单调队列优化dp）2014-01-03 csdn shuangde800题目大意

（LRJ《训练指南》）

有n个垃圾，第i个垃圾的坐标为（xi,yi），重量为wi。有一个机器人，要按照编号从小到大的顺序捡起所有垃圾并扔进垃圾桶（垃圾桶在原点（0,0））。机器人可以捡起几个垃圾以后一起扔掉，但任何时候其手中的垃圾总重量不能超过最大载重C。两点间的行走距离为曼哈顿距离（即横坐标之差的绝对值加上纵坐标之差的绝对值）。求出机器人行走的最短总路程（一开始，机器人在（0,0）处）。

【输入格式】

输入的第一行为数据组数。每组数据的第一行为最大承重C（1≤C ≤100）；第二行为正整数n（1≤n≤100 000），即垃圾的数量；以下n行每行为两个非负整数x, y和一个正整数w，即坐标和重量（重量保证不超过C）。

【输出格式】

对于每组数据，输出总路径的最短长度。

思路

方法一：

sumDis[i], 表示从0->1->2->....->i，即从0一直走到i个总距离

sumWeight[i], 表示前i个垃圾的总重量

假设要捡（j, i）这区间内的垃圾,

令 w（j,i） = sumWeight[i] - sumWeight[j-1]; 表示（j,i）区间垃圾的总重量

机器人的走路路径为：0- >j->j+1->..->i->0,这段路的总距离为:

routeDist（j, i） = getDis（0, j） + sumDis[i] - sumDis[j] + getDis（0, i）

设f（i）表示捡完前i个垃圾走的最短距离，那么可得到状态转移

f（i） = min{ f（j-1） + routeDist（j, i）, 1<=j<=i && sumWeight[i]-sumWeight[j-1] >= C }

代码一

/**==========================================* This is a solution for ACM/ICPC problem** @source：uva-1169 Robotruck* @type: dp* @author: shuangde* @blog: blog.csdn.net/shuangde800* @email: zengshuangde@gmail.com*===========================================*/#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<cmath>#include<cstring>using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 100010;int C, n;int sumDis[MAXN], sumWeight[MAXN];int f[MAXN];struct Node{int x, y, w;}A[MAXN];int getDis（int i, int j） {return abs（A[i].x-A[j].x） + abs（A[i].y-A[j].y）;}int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--） {scanf（"%d%d", &C, &n）;for（int i = 1; i <= n; ++i） {scanf（"%d%d%d", &A[i].x, &A[i].y, &A[i].w）;sumDis[i] = sumDis[i-1] + getDis（i, i-1）;sumWeight[i] = sumWeight[i-1] + A[i].w;}for（int i = 1; i <= n; ++i） {f[i] = INF;for（int j = i; j >= 1; --j） {int w = sumWeight[i] - sumWeight[j-1];if（w > C） break;int dis = getDis（0, j） + sumDis[i] - sumDis[j] + getDis（0, i）;f[i] = min（f[i], f[j-1]+dis）;}}printf（"%d
", f[n]）;if（nCase） putchar（"
"）;}return 0;}