题解

题解

#include<bits/stdc++.h>
using namespace std;
int n,m,t[505],mem[505][505];
int solve(int i,int st)
{
if (i == n + 1)
return 0;
if (st < t[i])
return solve(i,t[i]);
if (mem[i][st - t[i]])
return mem[i][st - t[i]];
int sum = 0,j = i;
#while (j <= n && t[j] <= st)
sum += t[j++];
int best = st * (j - i) - sum + solve(j,st + m);
for (;j <= n;j++)
{
sum += t[j];
best = min(t[j] * (j - i + 1) - sum + solve(j + 1,t[j] + m),best);
}
return mem[i][st - t[i]] = best;
}
int main(void)
{
cin >> n >> m;
for (int i = 1;i <= n;i++)
{
cin >> t[i];
}
sort(t + 1,t + n + 1);
cout << solve(1,0) << endl;
return 0;
}