题目大意
(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\n", f[n]);
if(nCase) putchar('\n');
}
return 0;
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数据
， 路径最短
， 机器人
， 算法训练
， 整数
， 区间
， 绝对值
， 坐标距离
垃圾
海尔1169、169、601169、1169万韩元、1069，以便于您获取更多的相关知识。