摆渡车

做法：记忆化搜索

思路：

• 1.小于等于当前时间点的人都要上车
• 2.当前时间没人就跳到下一个有人的时间点
• 3.考虑是不是要等待下一个人来再开车

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=510;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m;
int dp[N][N],ans=INF;
int t[N];

int dfs(int i,int time){ //i表示完成人数,time表示当前时间 
    if(i==n) return 0;
    if(time<t[i]) return dfs(i,t[i]);
    if(dp[i][time-t[i]]) return dp[i][time-t[i]];

    int j=i,sum=0;
    while(j<n&&t[j]<=time) sum+=t[j++];
    int res=time*(j-i)-sum+dfs(j,time+m);
    for(;j<n;j++){
        sum+=t[j];
        res=min(res,t[j]*(j-i+1)-sum+dfs(j+1,t[j]+m));
    }
    return dp[i][time-t[i]]=res;
}

void solve(){
    cin>>n>>m;
    _for(i,n) cin>>t[i];
    sort(t,t+n);
    cout<<dfs(0,0)<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
//     int t;cin>>t;while(t--)
    solve();
    return 0;
}