题意：有n个垃圾，坐标为（xi,yi）重量为wi。有一个机器人，要按照编号从小到大的顺序捡起所有垃圾并扔进垃圾桶（坐标（0，0））。机器人可以捡起几个垃圾以后一起扔掉，但任何时候其手中的垃圾总重量不能超过C.两点间的行走距离为曼哈顿距离。求出机器人行走的最短距离。

设dp[i]为机器人清理完前i个垃圾所走的最短路程，则,

dp[i]=min{dp[j]+dist(0,j+1)+dist(j+1,j+2)+dist(j+2,j+3)...+dist(i-1,i) + dist(i,0) | j<i,sumw[j+1...i]<=C};0为原点

用totald[i]表示dist(O,1)+dist(1,2)+..+dist(i-1,i)

则dist(j+1,j+2)+...+dist(i-1,i)=totald[i]-totald[j+1];

dp[i]=min{dp[j]+dist(0,j+1)-totald[j+1] | j<i,sumw[j+1...i]<=C }+totald[i]+dist(0,i);

可用单调队列优化

const int maxn=100100;int dp[maxn],totald[maxn],totalw[maxn];int x[maxn],y[maxn],w[maxn];int dist(int a,int b){    return abs(x[a]-x[b])+abs(y[a]-y[b]);}int f(int id){    return dp[id]+dist(0,id+1)-totald[id+1];}int q[maxn];int work(int n,int c){    int front=1,rear=2;    dp[0]=0;    q[1]=0;    for(int i=1;i<=n;i++)    {        while(rear>front&&totalw[i]-totalw[q[front]]>c)front++;        dp[i]=f(q[front])+dist(i,0)+totald[i];        while(rear>front&&f(i)