updated on 2018.11.17：
1. 之前所说的最后一项优化经检验发现有\(bug\)，已经去掉；
2. 对文中的一些错误进行了修改，同时对文章的行文作了一些调整，便于大家理解。建议大家在博客里食用：
要是PJ组再考这么难的DP，我就当官把CCF取缔了
开个玩笑。
此题正解：\(\mathrm{DP}\)+各种剪枝 or 优化
一、引理
对于每个乘客，能搭载ta的车的发车时间只有\(m\)种情况；
设这个乘客开始等候的时间是\(t_i\)，则对应的\(m\)种情况是\([t_i,t_i+m)\)（方括号 和 圆括号 表示左闭右开区间）。
证明
如果存在一种情况，其发车时间是\(\geqslant t_i+m\)的，则由题意可知，发车时间可以提早若干轮（也就是减去若干个\(m\)）到达\([t_i,t_i+m)\)这个区间，这样做不会影响发车时间\(\geqslant t+m\)的那趟车，不会有后效性。
如果\(<m\)的话，那这个乘客根本就坐不上这趟车，所以不需要考虑。
二、基本思想
首先，题目给定我们的这\(n\)个人开始等候的时间是乱的，所以我们要先按照开始等车的时间把这\(n\)个人排个序。
设\(f[i][j]\)表示用摆渡车已经载了前\(i\)个人，且搭载了第\(i\)个人（不一定只搭载第\(i\)个人）的那趟摆渡车的发车时间是（\(t_i+j\)）的最小等候时间和。（\(t_i\)的意义与题意相同）
这里要注意：\(t_i+j\)同时还需要满足\(t_i+j<t_{i+1}\)
因为如果\(\geqslant t_{i+1}\)，那这趟车就可以把第\(i+1\)个人也搭上了，违反了\(\mathrm{DP}\)状态的定义。对于每个\(f[i][j]\)，枚举上一趟摆渡车的出发时间。
等等！数据范围写着：
\[1 \leqslant t_i \leqslant 4\times10^6 \]
你跟我说枚举时间？你这最起码都\(O(n*t_i) \sim O(2\times10^9)\) 的时间复杂度了，怎么\(AC\)？
别着急啊，我还没说完呢。
其实引理已经告诉我们，我们不需要把整个\(t_i\)枚举完。
由引理可得，对于前\(i-1\)个乘客，每个乘客能搭载的摆渡车的发车时间只有\(m\)种情况，所以我们只需要枚举这\((i-1)\times m\)种情况即可。其他情况都是废的，不需要去考虑。
这样做的枚举量为\(O(nm) \sim O(5 \times 10^4)\)，相比之前直接枚举\(t_i\)的时间复杂度\(O(4 \times 10^6)\)来讲，已经是飞跃了。
接着，假设前一趟摆渡车已经载了前\(k\)个人，那么我们要做的就只有两件事：
- 再枚举一个\(l\)，得到\(f[k][l]\)的最小值。
- 计算出第\(k+1\)个人到第\(i\)个人等候当前这趟摆渡车的等候时间和。
在状态转移方程中的体现就是：
\[f[i][j]=\min_{0 \leqslant k < i,0 \leqslant l < m} \{f[k][l]+col(k+1,i,t_i+j)\}\]
这当中，\(col(k+1,i,t_i+j)\)表示第\(k+1\)个乘客到第\(i\)个乘客等候发车时间为\(t_i+j\)的那趟摆渡车的时间和。
这里也有一个地方要注意：在枚举\(k\)和\(l\)时，要满足\(t_k+l<t_{k+1}\)。
理由和上面一样，是因为这样做违反了\(\mathrm{DP}\)中状态的定义。其实上面的这个状态转移方程并不严谨，不过本人会慢慢把它修改得严谨起来（其实下文中的修改过程就是本人在考场上的思路）。
但这个方程很重要，以后的所有优化全都源自于这个方程，为了节省篇幅，本人不会重述这个方程，所以请大家记住这个转移方程。
先抛开正确性，我们可以来计算一下上面这个状态转移方程的时间复杂度。
- 首先，\(i\)和\(j\)必须枚举，所以是\(O(nm)\)的时间复杂度。
- 其次，\(k\)和\(l\)也是要枚举的，所以又是一个\(O(nm)\)。
- 最后，每次枚举\(i,j,k,l\)，都要计算一次\(col\)函数，而这个\(col\)函数的时间复杂度是\(O(n)\)的。
综上所述，这个状态转移方程的时间复杂度为\(O(nm)*O(nm)*O(n)=O(n^3m^2)\)。
这时间复杂度……也太
可观了吧所以我们需要优化！优化！优化！
三、程序实现 or 剪枝
我们可以发现，这\(n\)个人中有一些人开始等候的时间是相同的。
对于这些人，我们可以进行去重（开一个结构体，把相同时间的人压进一个结构体里面，结构体里则用一个变量表示这些人开始等候的时间，用另一个变量表示这些重复的人的人数）。
虽然这样做时间复杂度会多增加了\(O(n\log n)\)，但这样可以在\(\mathrm{DP}\)时减少很多繁琐的特判。
我们来关注一下这个式子：\[col(k+1,i,t_i+j)\]
对于每个\(i,j\)，当\(k\)每增加一时，\(col\)的值就只会减掉\((t_i+j-t_k)*size_k\)（\(size_k\)表示结构体中第\(k\)个元素的重复的人的数量）。所以我们可以在枚举每个\(i\)和\(j\)时，就把\(col(k+1,i,t_i+j)\)算出来（用一个变量\(val\)存起来），然后，每当\(k\)增加\(1\)，\(val\)就减去\((t_i+j-t_k)*size_k\)。
状态转移方程就变为：\[f[i][j]=\min_{0 \leqslant k < i,0 \leqslant l < m} \{f[k][l]+val\}\]
这样一抽出来，时间复杂度就变成了\(O(nm(n+nm))=O(n^2m+n^2m^2)\)
只保留最高次项后，时间复杂度就降为了\(O(n^2m^2)\)！！！又是一个飞跃！！！
注意！接下来的内容全都是难点，请大家做好心理准备！
其实大家有没有想过，枚举\(l\)这个操作显得有些多余，可不可以省去呢？（毕竟只是求一个最小值而已，我求完一次就把这个最小值存起来不就行了吗？）
没错，上面的想法是正确的！
设
\[Min[i]= \min_{0 \leqslant j < m,t_i+j<t_{i+1}} \{f[i][j]\}\]则之前的状态转移方程可以简化为：
\[f[i][j]=\min_{0 \leqslant k < i} \{Min[k]+val\}\]
\(Min[k]\)可以在求每个\(f[k][l]\)的时候顺带维护
因为这里只枚举了\(i,j,k\)，所以\(\mathrm{DP}\)的时间复杂度是\(O(n^2m)\)！！！
## 这个时间复杂度足以通过本题了！！！
但是，这样做真的是对的吗？
假设有这样一个例子：
（数轴上的两个点表示的是乘客开始等候的时间，圈3和圈4表示两个乘客在（结构体）数组中的编号）
这时，我们直接用\(Min[3]\)来为\(f[4]\)做\(\mathrm{DP}\)就不行了。
假设我们要求\(f[4][0]\)的值（也就是说最后一趟车的发车时间和第4个乘客开始等候的时间相同的情况），当我们枚举到\(k=3\)的情况时，我们只能取\(0 \leqslant l \leqslant 1\)的情况。（如果\(l>1\)的话，前一趟车的时间就有可能和当前这趟车的时间重叠了，违反了\(\mathrm{DP}\)中状态的定义！）
也就是说，不能直接用\(Min\)数组来\(\mathrm{DP}\)！（因为\(Min[3]\)包含了\(f[3][0]\)到\(f[3][4]\)的最小值，直接用会出错！）
那应该怎么办？（我在考场上最绝望的时刻就是思考这个问题的过程）
后来一想：可不可以直接特判呢？
## 事实证明，可以！
首先，对于每个\(i,j\)，我们都为其开一个变量\(lt=t_i+j-m\)作为一个“防护墙”。
对于每个\(k\)，如果\(t_k+m>lt\)，那么\(Min[k]\)就不适用于\(f[i][j]\)这个状态（因为对于这个\(k\)，有些\(t_k+l\)加上\(m\)以后会和\(t_i+j\)重叠）
对于这些\(k\)，我们就重新帮它枚举一个\(l\)（满足\(t_k+l \leqslant lt\)，不然超过了会重叠）去\(\mathrm{DP}\)。
由此也可以得出，如果\(t_k>lt\)，就可以直接退出当前循环了。（因为你没有\(l\)再去枚举了）
这样一来，状态转移方程就开始有些恶心了：
\[f[i][j]=\begin{cases} \min\ \{Min[k]+val\} & t_k+m \leqslant lt \\ \min\limits_{t_k+l \leqslant lt} \{ f[k][l]+val \} & t_k+m>lt \end{cases}\]
这样优化后的时间复杂度是多少呢？
首先，无论如何，\(i(n)\)和\(j(m)\)是一定要枚举的，所以时间复杂度至少会有\(O(nm)\)。
然后，我们可以把两个方程分开考虑：
第一个方程枚举了\(k(n)\)，时间复杂度为\(O(n)\)
因为\(k\)和\(l\)总共只会计算\(m\)次（因为只有当\(lt-t_k<m\)时才会进入第二种情况。而\(l\)每次至少增长\(1\)，最慢也就是\(O(m)\)而已）
所以第二条方程的时间复杂度为\(O(m)\)。
加起来就是\(O(nm(n+m))\)，因为\(n>m\)，所以可以简化成\(O(n^2m)\)！这个时间复杂度可以通过本题！
至此，我们终于得出了此题的可行解法！
四、考场代码
我的代码在结构体边界上有一些预处理，这个重在意会即可相信大家应该看得懂
#include#include using namespace std;const int maxn=502,maxm=102;const int INF=0x7fffffff;int f[maxn][maxm];int Min[maxn];int a[maxn];struct Node{ int pos,num;}Mem[maxn];int sz;int col(int l,int r,int pos){ int res=0; for(int i=l;i<=r;i++) res+=(pos-Mem[i].pos)*Mem[i].num; return res;}int main(int argc, char const *argv[]){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); Mem[0].pos=-m*2-2; a[0]=-1; for(int i=1;i<=n;i++) { if( a[i]^a[i-1] ) Mem[++sz].pos=a[i]; Mem[sz].num++; } Mem[sz+1].pos=Mem[sz].pos+m+2; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f[i][j]=INF; Min[i]=INF; } Min[0]=0; for(int i=1;i<=sz;i++) for(int j=0;j
\(In\ a\ word\)，祝大家\(\mathrm{NOIP\ rp}\)++！