LA 3983 - Robotruck

 1 /*
 2 author:jxy
 3 lang:C/C++
 4 university:China,Xidian University
 5 **If you need to reprint,please indicate the source**
 6 */
 7 #include <iostream>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <algorithm>
12 using namespace std;
13 int Cap,n;
14 int dis2org[100005]; //到原点距离
15 int dis[100005],cap[100005];//从0到i的距离
16 int abs(int x){return x>0?x:-x;}
17 int ans[100005];
18 int que[100005];
19 int calc(int i)
20 {
21     return ans[i]+dis2org[i+1]-dis[i+1];
22 }
23 int main()
24 {
25     int T;
26     scanf("%d",&T);
27     while(T--)
28     {
29         scanf("%d%d",&Cap,&n);
30         int i,x,y,c,lx=0,ly=0,l,r;
31         dis[0]=cap[0]=0;
32         for(i=1;i<=n;i++)
33         {
34             scanf("%d%d%d",&x,&y,&c);
35             dis2org[i]=abs(x)+abs(y);
36             cap[i]=cap[i-1]+c;
37             dis[i]=dis[i-1]+abs(x-lx)+abs(y-ly);
38             lx=x;ly=y;
39         }
40         l=r=0;
41         ans[0]=0;
42         for(i=1;i<=n;i++)
43         {
44             while(l<r&&cap[i]-cap[que[l]]>Cap)l++;
45             while(l<r&&calc(i-1)<=calc(que[r-1]))r--;//维护单调队列
46             que[r++]=i-1;
47             ans[i]=calc(que[l])+dis[i]+dis2org[i];
48         }
49         printf("%d\n",ans[n]);
50         if(T)puts("");
51     }
52 }