未用斜率优化写的一种不太优美的DP，WAon#9#10#16求调。

Code:

#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, maxn, temp, t[505], t1[4000005], t2[4000005], sum1[4000005], sum2[4000005], f[4000005];

int main()
{
	scanf("%d%d", &n, &m);
	for (register int i = 1; i <= n; ++i)
	{
		scanf("%d", t + i);
		maxn = max(maxn, t[i]);
		++t1[t[i]];
		t2[t[i]] += t[i];
	}
	temp = maxn + m;
	for (register int i = 0; i < temp; ++i)
	{
		sum1[i] = sum1[i - 1] + t1[i];
		sum2[i] = sum2[i - 1] + t2[i];
		f[i] = sum1[i] * i - sum2[i];
	}
	for (register int i = 0; i < temp; ++i)
	{
		if (i >= m && sum1[i - m] * i == sum1[i])
		{
			f[i] = f[i - m];
		}
		else
		{
			for (register int j = max(i - m * 2 + 1, 0); j <= i - m; ++j)
			{
				f[i] = min(f[i], f[j] - sum2[i] + sum2[j] + (sum1[i] - sum1[j]) * i);
			}
		}
	}
	printf("%d", *min_element(f + maxn + 1, f + temp));
	return 0;
}

不理解为什么第二个样例总是输出 $5$ 。