摆渡车—线性dp

#include<bits/stdc++.h>
using namespace std;

int n,m,a[505],f[510][110],inf;
int s[505],t[505];

int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(f,0x3f,sizeof f);inf=f[0][0];
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+t[i];
	//dp
	t[0]=-inf;//第零个人不存在 ，在数轴最左端 
	f[0][0]=0;
	for(int i=0;i<n;i++) 
	{
		int Max=min(m-1,t[i+1]-t[i]);
		for(int j=0;j<=Max;j++)
		{
			if(f[i][j]!=inf)//由已经计算过的状态去计算下一个未知状态 ，技巧是刷表法 
			{
				for(int k=1;k+i<=n;k++)//枚举下一个人 
			    {
				    int tmp=max(t[i]+j+m-t[i+k],0);//tmp 是k要等多久时间，才能等到到A地的车 
				    int T=tmp+t[i+k];//T 是到车时间 
				    f[k+i][tmp]=min(f[k+i][tmp],f[i][j]+T*k-s[k+i]+s[i]);
			    }
			}
		}
	}
	int res=inf;
	for(int i=0;i<m;i++) res=min(res,f[n][i]);
	cout<<res;
}