题意：有n个垃圾，第i个垃圾坐标为(xi，yi)。有一个机器人按照编号从小到大哦捡起所有的垃圾并扔进垃圾桶，垃圾桶再远点。机器人手中垃圾总重量不能超过C，两点之间的距离为曼哈顿距离，求机器人行走的最短总路程
分析：d[i]=min{d[j]+dist2origin(j+1)+dist(j+1,i)+dist2origin(i)|j<=i, w(j+1,i)<=c}
里面可以写成函数f以简化计算
代码：
View Code 1 #include2 #include 3 using namespace std; 4 const int MAXN = 100000 + 10; 5 int x[MAXN], y[MAXN]; 6 int total_dist[MAXN], total_weight[MAXN], dist2origin[MAXN]; 7 int q[MAXN], d[MAXN]; 8 #define DEBUG 9 int func(int i){10 return d[i]-total_dist[i+1]+dist2origin[i+1];11 }12 13 int main(){14 #ifndef DEBUG15 freopen("in.txt", "r", stdin);16 #endif17 int T, c, n, w, front, rear;18 scanf("%d", &T);19 while(T--){20 scanf("%d%d", &c, &n);21 total_dist[0] = total_weight[0] = x[0] = y[0] = 0;22 int i;23 for(i=1; i<=n; i++){24 scanf("%d%d%d", &x[i], &y[i], &w);25 dist2origin[i] = abs(x[i])+abs(y[i]);26 total_dist[i] = total_dist[i-1] + abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);27 total_weight[i] = total_weight[i-1] + w;28 }29 front = rear = 1;30 for(i=1; i<=n; i++){31 while(front<=rear && total_weight[i]-total_weight[q[front]]>c) front++;32 d[i]=func(q[front])+total_dist[i]+dist2origin[i];33 while(front<=rear && func(i)<=func(q[rear])) rear--;34 q[++rear] = i;35 }36 printf("%d\n", d[n]);37 if(T>0) printf("\n");38 }39 return 0;40 }
今天感觉做题目不很在状态，直接看了训练指南上的分析。。