Description：
有 n 名同学要乘坐摆渡车从人大附中前往人民大学，第 i位同学在第 t 分钟去 等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费m分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。
凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？
Hint:
(n,m<=500,t<=4*10^6)
Solution:
比较好的一道线性dp
[f[i+m+j]=sum min(f[i]+s[i+m+j]-s[i]+b[i]*(m+j))
]
((0 le j<m))
其中：
(s_i表示从1到i所有人等车时间的前缀和，b_i表示人数的前缀和)
#include<bits/stdc++.h>
using namespace std;
const int mxn=5050,mxt=4e6+5;
int n,m,T,t=mxt,ans=mxt;
int a[mxn],b[mxt],f[mxt],s[mxt];
inline void checkmax(int &x,int y) {if(x<y) x=y;}
inline void checkmin(int &x,int y) {if(x>y) x=y;}
int main()
{
scanf("%d%d",&n,&m); memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i) {
scanf("%d",a+i); ++b[a[i]];
checkmin(t,a[i]),checkmax(T,a[i]);
}
sort(a+1,a+n+1); int cnt=1,tot=0;
for(int i=0;i<=T+2*m;++i) {
while(i>a[cnt]&&cnt<=n) ++tot,++cnt;
b[i]+=b[i-1];
s[i]=s[i-1]+tot;
}
f[0]=0;
for(int i=0;i<=T+2*m;++i) f[i]=s[i];
for(int i=0;i<=T+m;++i) {
checkmin(f[i+m],f[i]+(s[i+m]-s[i])-b[i]*m);
for(int j=1;j<m;++j)
if(b[i]!=b[i+m+j]) //剪枝，最多转移到i+m
checkmin(f[i+m+j],f[i]+(s[i+m+j]-s[i])-b[i]*(m+j));
}
for(int i=T;i<=T+m;++i) checkmin(ans,f[i]);
printf("%d",ans);
return 0;
}