摆渡车

可以设dp[i]表示从第i个人的时间点发一班车，前面i个人的最小等待时间
但在这之前需要把t[i]排序，应为题目中并没有说输入一定是递增的（第一次死在了这里
然后枚举k和i，dp[i] = min(dp[k] + cost(k,i),dp[i])
可以这么想想吧,在前k个时间的时候已经开出了x次(x不重要，然后我们可以满足在k点发一班车，这是就要计算赶不上这班车等着下一班车的人的所有等待时间了，这里的等待时间可以用前缀和计算（前缀和：是一个数列为1 2 3 5 2 5 6 2 6它的前缀和就是1 3 6 11 13 18 24 26 32本蒟蒻一开始前缀和都忘了

那为什么可以拿前缀和来算呢，一开始看到题解在这里卡了很久

多用几个样例可以发现他们的等待时间和前缀和有关，就比如说第一个人是第1分钟来的，第二个人是第3分钟来的，第3个人是第7分钟来的，并假设他们都是第10分钟走，第一个人等待9分钟，第二个人等待7分钟，第3个人等待3分钟发现当我们想算sum(k+1,i)的时候，就是算s[i]-s[k](s为前缀和数组

#include<bits/stdc++.h>
using namespace std;
int n,m,a[505],s[505],dp[505][505];
int sum(int l,int r)
{
 return s[r]-s[l-1];
} 
int main()
{
 cin>>n>>m;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 sort(a+1,a+1+n);
 for(int i=1;i<=n;i++)
  s[i]=s[i-1]+a[i];
 memset(dp,0x3f,sizeof(dp));
 for(int i=1;i<=n;i++)
 {
  dp[i][0]=i*a[i]-sum(1,i);
  for(int j=0;j<m;j++)
  {
   for(int k=1;k<i;k++)
   {
    int x=min(m-1,a[i]+j-a[k]-m);
    if(x<0)
     continue;
    dp[i][j]=min(dp[i][j],dp[k][x]+(i-k)*(a[i]+j)-sum(k+1,i));
   }
  }
  for(int j=1;j<m;j++)
   dp[i][j]=min(dp[i][j],dp[i][j-1]);
 }
 printf("%d\n",dp[n][m-1]);
 return 0;
}