这道题感觉挺吃力的，还用到了我不熟悉的优先队列
题目中的推导也都看明白了，总之以后还要多体会才是
这里用优先对列的原因就是因为要维护一个滑动区间的最小值，比如在区间里２在１的前面，２在离开这个滑动区间会一直被１给“压迫”着，所以这个２是无用的，应当及时删除。这样的话剩下的元素都是递增的，优先队列也称单调队列也因此得名。
先把代码贴上：
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
int x[maxn], y[maxn];
int total_dist[maxn], total_weight[maxn], dist2origin[maxn];
int q[maxn], d[maxn]; int func(int i)
{
return d[i] - total_dist[i+] + dist2origin[i+];
} int main(void)
{
#ifdef LOCAL
freopen("3983in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
int c, n, w, front, rear;
scanf("%d%d", &c, &n);
total_dist[] = total_weight[] = x[] = y[] = ;
for(int i = ; i <= n; ++i)
{
scanf("%d%d%d", &x[i], &y[i], &w);
dist2origin[i] = x[i] + y[i];
total_dist[i] = total_dist[i-] + abs(x[i] - x[i-]) + abs(y[i] - y[i-]);
total_weight[i] = total_weight[i-] + w;
}
front = rear = ;
for(int i = ; i <= n; ++i)
{
while(front <= rear && total_weight[i] - total_weight[q[front]] > c)
++front;
d[i] = func(q[front]) + total_dist[i] + dist2origin[i];
while(front <= rear && func(q[rear]) >= func(i))
--rear;
q[++rear] = i;
}
printf("%d\n", d[n]);
if(T) printf("\n");
}
return ;
}
代码君