LA 3983 Robotruck/単調キュー
1717 ワード
n個のゴミロボット(0,0)から順番にゴミを拾って原点に戻って複数持ち帰ることができ、重量の和がCより大きくならない
構想とコードはすべて本の上のを参考にして最小の距離を歩いたことを求めます
2点の距離はabs(x 1-x 2)+abs(y 1-y 2)
dp(i)は、i番目のゴミを拾い終えて原点に戻る最小距離
dis(i)原点からi番目のゴミまでの記録
dist(i)は、1番目から2番目から3番目からi番目のゴミを通過する距離であり、j番目からi番目のゴミまでの距離はdist(i)−dis(j)である.
w(i,j)は、i番目からj番目のごみの重量の和を表す
dp(i)=dp(j)+dis(j+1)+dist(i)−dist(j+1)+dis(i)=dp(j)−dist(j+1)+dis(j+1)+dis(i)+dist(i)およびw(j+1,i)<=C
このようにiについてすべて提出します
jを考慮して最小のdp(j)-dist(j+1)+dis(j+1)を求めるだけで列挙jがタイムアウトする
現在求められているのは,j最小値は単調なキューで維持できます
構想とコードはすべて本の上のを参考にして最小の距離を歩いたことを求めます
2点の距離はabs(x 1-x 2)+abs(y 1-y 2)
dp(i)は、i番目のゴミを拾い終えて原点に戻る最小距離
dis(i)原点からi番目のゴミまでの記録
dist(i)は、1番目から2番目から3番目からi番目のゴミを通過する距離であり、j番目からi番目のゴミまでの距離はdist(i)−dis(j)である.
w(i,j)は、i番目からj番目のごみの重量の和を表す
dp(i)=dp(j)+dis(j+1)+dist(i)−dist(j+1)+dis(i)=dp(j)−dist(j+1)+dis(j+1)+dis(i)+dist(i)およびw(j+1,i)<=C
このようにiについてすべて提出します
jを考慮して最小のdp(j)-dist(j+1)+dis(j+1)を求めるだけで列挙jがタイムアウトする
現在求められているのは,j
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int x[maxn], y[maxn], w[maxn];
int dist[maxn], weight[maxn], dis[maxn];
int q[maxn], dp[maxn];
int func(int i)
{
return dp[i] - dist[i+1] + dis[i+1];
}
int main()
{
int T;
int C, n, front, rear;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &C, &n);
for(int i = 1; i <= n; i++)
{
scanf("%d %d %d", &x[i], &y[i], &w[i]);
dist[i] = dist[i-1] + abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);
dis[i] = abs(x[i]) + abs(y[i]);
weight[i] = weight[i-1] + w[i];
}
front = rear = 1;
for(int i = 1; i <= n; i++)
{
while(front <= rear && weight[i] - weight[q[front]] > C)
front++;
dp[i] = func(q[front]) + dis[i] + dist[i];
while(front <= rear && func(i) <= func(q[rear]))
rear--;
q[++rear] = i;
}
printf("%d
", dp[n]);
if(T)
puts("");
}
return 0;
}