做题感悟：这是接触的单调队列的第一题，终于把它弄懂了，结合白书以及网上的各种资料。
解题思路： 单调队列DP
这题的重点就在变换动态转移方程上，首先设 dp[ i ] 为处理到第 i 个垃圾所用的最小距离，那么很容易想到动态转移方程：dp[ i ] = min { dp[ j ] + d( j + 1 ) + d( j + 1 , i ) + d( i ) } 且 w( j + 1 , i ) <= W , 解释一下：d( i ) 为 i 点到原点的距离（指哈密顿距离），d( j + 1 ,i) 代表 从j + 1 到 i 的距离和。w(j + 1 , i ) 为从 j
+ 1 到 i 的重量和。W 为最大重量。
好了，接下来就是怎样去转化动态方程了：我们用前缀和的思想分别记录前缀距离和前缀重量，分别用数组 sumd[ i ] ,sumw[ i ] ,d[ i ] 为点i 到原点的距离，这样方程就可以变为：
dp[ i ] = min { dp[ j ] + d[ j +1 ] + sumd[ i ] - sumd[ j + 1] + d[ i ] } 且 sumw[ i ] - sum[ j ] <= W ;
进一步转变 ===>
dp[ i ] = min{dp[ j ] + d[ j + 1 ] - sumd[ j + 1 ] } + sumd[ i ] + d[ i ] ; 变成这样后你会发现前面的各个数只与本身相关，可以把他们放入一个队列中，只要维护队列的最小值（在重量满足的前提下），那么计算dp[ i ]的时间就变成O( 1 ) 的了。切记：队尾的结尾的元素为 end - 1
具体见代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT long long int
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<5) + 5 ;
const int MX = 100010 + 5 ;
int n ,W ;
int sumw[MX] ,d[MX] ,dp[MX] ,deq[MX] ,sumd[MX] ;
int Cavalue(int j)
{
return dp[j] + d[j+1] - sumd[j+1] ;
}
void input()
{
int x ,y ,w ;
scanf("%d%d" ,&W ,&n) ;
sumw[0] = sumd[0] = d[0] = 0 ;
int x1 = 0 ,y1 = 0 ;
for(int i = 1 ;i <= n ; ++i)
{
scanf("%d%d%d" ,&x ,&y ,&w) ;
sumw[i] = sumw[i-1] + w ; // 重量的前缀和
d[i] = abs(x) + abs(y) ; // 到原点的距离
sumd[i] = sumd[i-1] + abs(x-x1) + abs(y-y1) ; // 距离前缀和
x1 = x ;
y1 = y ;
}
}
void DP()
{
memset(deq ,0 ,sizeof(deq)) ;
int front = 0 ,end = 0 ; // deq 双端队列的头和尾
for(int i = 1 ;i <= n ; ++i)
{
while(front < end && Cavalue(deq[end-1]) >= Cavalue(i-1)) // 因为 end 没减一错了好久
end-- ;
deq[end++] = i-1 ;
while(front < end && sumw[i] - sumw[deq[front]] > W)
front++ ;
dp[i] = Cavalue(deq[front]) + d[i] + sumd[i] ;
}
}
int main()
{
int Tx ;
scanf("%d" ,&Tx) ;
while(Tx--)
{
input() ;
DP() ;
cout<<dp[n]<<endl ;
if(Tx) cout<<endl ;
}
return 0 ;
}