Robotruck 题目解析
题面 PDF
写在前面
有一说一，UVa 的输出真让人难绷。
教练在讲解这道题的时候，曾经嘲讽说这道题不配紫题，也不知道管理员能不能接纳这个意见吧难度降成蓝色。
然而这道题还是不很顺手，写个题解自己捋一捋思路吧。
参考了刘汝佳的紫书，并且尽量从我能理解的方向去阐明思路。
状态转移方程
这道题明显 DP。那么对于一道 DP 题，首先思考定义。
试定义：dp_i 为前 i 个元素中一口气运 i-j 个的最小代价，换而言之，过程被分解成了两部分：
第一步：先以最优方式运送 j 个垃圾；
第二步：一口气运送第 j+1 到 i 这么多垃圾。
若令distance_{i → j}表示 i 到 j 一共要走的路程（曼哈顿距离），那么则有：
dp_i=\min{dp_j+distance_{0 → j+1}+distance_{0 → i}+distance_{j+1 → i}}
所以 $j$ 的取值范围也不难得到：
$$j∈[0,i),\sum_{x=j+1}^{i}{weight_x}\le c$$
其中 $weight_x$ 代表了每个垃圾的质量。
代码实现也很方便，但是 $O(n^2)$ 的时间复杂度，显然不是我们希望的。
## 能不能更快一点？
如果使用前缀和解决这道问题，试定义：$dis\_m$ 表示用前缀和存储的两个点之间的曼哈顿距离，$dis\_back$ 表示每个点和原点之间的距离。
则上述状态转移方程变为：
$$dp_i=\min{dp_j+dis\_back_{j+1}+dis\_back_{i}+dis\_m_{i}-dis\_m_{j+1}}$$
显然，$dis\_back_{i}$ 和 $dis\_m_{i}$ 两个对于同一个 $i$ 而言是定量，不变，可以从 $\min$ 中提取出来。
则状态转移方程变为：
$$dp_i=\min({dp_j+dis\_m_{j+1}+dis\_back_{j+1}}) +dis\_m_{i}+dis\_back_{i}$$
若定义 $f_j=d_j+dis\_m_{j+1}+dis\_back_{j+1}$，那么状态转移方程进一步简化为：
$$dp_i=\min{\green{f_j}}+dis\_m_{i}+dis\_back_{i}\ \ (j∈[0,i),且\green{\sum_{x=j+1}^{i}{weight_x}\le c})$$
如果想优化，那么不难发现我标出绿色的两端是我们极力争取的。
1. 先思考 $\min{f_j}$，只要它合法，且没有比他更小的来替代它，那么此时对于 $dp_i$，选择谁呼之欲出。而且，在得到一个新 $dp_i$ 后，如果**此后**有一个比他小的数出现，那么，可以果断舍弃较大的。也许我们可以通过一个能把最小值直接送到我们面前的数据结构来解决这个问题。
2. 接着思考 $\sum_{x=j+1}^{i}{weight_x}\le c$，如果一个 $i$ 足够大，那么对于开始的若干个物品，我们认为他已经不合法了，而且未来也不会合法，对于这些数据，我们果断舍弃。
综上所述，我们可以使用**单调队列**优化这道题。
## 解决
首先，我们需要定义一个函数来计算上述的 $f_i$:
```c++
int com(int x){
return dp[x]-dis_m[x+1]+dis_back[x+1];
}
```
接着，就可以开始单调队列了。维护一个单增队列，同时动态队头出队：
```c++
front=rear=1;
for(int i=1;i<=n;i++){
while(front<=rear&&tot_weight[i]-tot_weight[q[front]]>c){
front++;
}
dp[i]=com(q[front])+dis_m[i]+dis_back[i];
while(front<=rear&&com(i)<=com(q[rear])){
rear--;
}
q[++rear]=i;
}
```
同时，输出的时候要注意，输出完一行空一行再输出，最后一个数据不输出多余的空行。UVa 老传统了。
还有一个小细节。在代码中可以看到我使用宏定义自己写了一个 ``abs``，而非使用 ``cmath`` 或``algorithm``，这是一个比较基本的原则：能不用上述的两个库（尤其是 ``cmath``）尽量不用，尤其是在单独用 ``abs`` 的时候，一行宏定义解决的问题就不要搞进来一堆函数。上述的两个库函数太多，容易起冲突。
## 代码
那么，代码解决也不难了，和其他题解大同小异，互相形成对照。
```c++
//exam name:[UVA1169]Robotruck
/*
dp[i] 表示前i个物品一口气运前j个的代价
dp[i]=min{dp[j]-dis_m(j+1)+dis_back(j+1)}+dis_m(i)+dis_back(i)
前j个物品运输代价+(j+1)到i的曼哈顿距离+去(j+1)的曼哈顿距离+回原点的曼哈顿距离
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#define abs(x) (((x)>0)?(x):(-(x)))
#define int long long
using namespace std;
const int MAXN=100005;
int com(int);
int dp[MAXN],dis_m[MAXN],dis_back[MAXN],tot_weight[MAXN];
int x[MAXN],y[MAXN],w[MAXN];
int q[MAXN];
int front,rear;
int t,c,n;
signed main(){
cin>>t;
for(int kase=1;kase<=t;kase++){
memset(dis_m,0,sizeof(dis_m));
memset(dis_back,0,sizeof(dis_back));
memset(tot_weight,0,sizeof(tot_weight));
x[0]=y[0]=0;
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>w[i];
dis_back[i]=abs(x[i])+abs(y[i]);
dis_m[i]=dis_m[i-1]+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
tot_weight[i]=tot_weight[i-1]+w[i];
}
front=rear=1;
for(int i=1;i<=n;i++){
while(front<=rear&&tot_weight[i]-tot_weight[q[front]]>c){
front++;
}
dp[i]=com(q[front])+dis_m[i]+dis_back[i];
while(front<=rear&&com(i)<=com(q[rear])){
rear--;
}
q[++rear]=i;
}
cout<<dp[n]<<endl;
if(kase<t){
puts("");
}
}
return 0;
}
int com(int x){
return dp[x]-dis_m[x+1]+dis_back[x+1];
}
```
## 写在后面
本人蒟蒻，某些地方没有讲清楚的什么的可以联系我，我会及时极力修改，感谢大家支持！