LA 3983 - Robotruck
7746 ワード
に言及
1つの掃除ロボットは順番にすべてのごみを収集して、最小のステップ数を求めます
グループ数T
ロボット容量Cap
ごみの数n
ごみ座標と重量x y c
てんいほうていしき
\( d(i)=min\{d(j)+dis2org(j+1)+dis(j+1,i)|j(dis(j+1,i)=dis(i)−dis(j))とすると、(d(i)=min{d(j)+dis 2 org(j+1)−dis(j+1)}+dis(i)+dis 2 org(i))となる
1つの掃除ロボットは順番にすべてのごみを収集して、最小のステップ数を求めます
グループ数T
ロボット容量Cap
ごみの数n
ごみ座標と重量x y c
てんいほうていしき
\( d(i)=min\{d(j)+dis2org(j+1)+dis(j+1,i)|j
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
",ans[n]);
50 if(T)puts("");
51 }
52 }