NOIp2018 보급팀 - 나룻배

(보급팀을 떠난 은퇴 선수로서 다행이다)
제목 링크:https://www.luogu.org/problemnew/solution/P5017
1. 느낌은 일종의 선형적인 시간을 차원으로 하는 dp이다. 다시 한 번 범위: 4*10^6는 큰 문제가 없다.
2. f[t]의 의미에 대해 생각하기 시작한다. 나룻배가 t분에 떠날 때 모든 사람이 가장 적은 대기 시간을 갖는다.
3. 이어서 이동: 우선 t보다 일찍 출발 2*m 분 전(낭비야)의, m분 후의(이동 불가) 모두 고려하지 않아도 된다
4. 마지막으로 j가 i-2*m에서 i-m로 이동하는 방안을 매거하고 이 시간 동안의 이동을 더하면 우리의 답이다.
(5. 하지만 CCF의 기계는 한마디로 말하기 어려우니 최적화를 고려해보자...i-m 사이에 아무도 없다면 i는 사실 직접 값을 부여할 수 있으니 계산하지 않아도 된다)
over

#include 

using namespace std;
const int maxn=5000005;
int t[maxn],num[maxn],st[maxn],f[maxn];int T=0;
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t[i]);num[t[i]]++;
		T=max(T,t[i]);
		st[t[i]]+=t[i];
	}
	for(int i=1;i<=T+m-1;i++)
	{
		num[i]+=num[i-1];st[i]+=st[i-1];
	}
	int minv=0x3f3f3f3f;
	for(int i=1;i<=T+m-1;i++)
	{
		if(i>=m&&num[i-m]==num[i]) {f[i]=f[i-m];continue;}//     ，       
		f[i]=num[i]*i-st[i];
		for(int j=i-m;j>=max(0,i-2*m);j--)
		{
			f[i]=min(f[i],f[j]+(num[i]-num[j])*i-(st[i]-st[j]));
		}
	}
	for(int i=T;i<=T+m-1;i++) minv=min(minv,f[i]);
	printf("%d",minv);
	return 0;
 }