将时间抽象为一根数轴,将其分为k段,每一段中的右端点表示当前端点发了一班车,此时t<=i的旅客均可上车。

而对于一个位于j(j<=i)位置的旅客,其等车时间为(i-j)。我们需要求出位于区间(??,i]内旅客等车时间总和。可以用前缀和优化这个步骤。

具体操作为使用两个前缀和,第一个cnt记录(i,j]中的旅客个数,第二个sum记录(i,j]的时间差,则dis=(cnt[j]-cnt[i])*i-(sum[j]-sum[i])

dp[i]表示(-∞,i]以i为最后一段的结尾时产生的总代价。

显然,对于一个位置i,其可能来自的位置为[i-2m,i-m](<=i-2m的其他位置ans不会更优),因此,上文(??,i]的枚举范围便为[i-2m,i-m]

还有一个比较显然的优化:当当前枚举的区域[j,i]内没有旅客时,我们可以直接继承dp[i-m]的答案并跳过这个时间点。

/* int n,m,T,tmp;
int cnt[4000005],dis[4000005],dp[4000005];
int main() {
	n=read(),m=read();
	for(int i=1; i<=n; i++)
		tmp=read(),T=max(T,tmp),cnt[tmp]++,dis[tmp]+=tmp;
	for(int i=1; i<m+T; i++)cnt[i]+=cnt[i-1],dis[i]+=dis[i-1];
	for(int i=0; i<m+T; i++) {
		dp[i]=cnt[i]*i-dis[i];
		for(int j=i-2*m>0?i-2*m:0; j<=i-m; j++)//此处防止左边界越界
			dp[i]=min(dp[i],dp[j]+(cnt[i]-cnt[j])*i-dis[i]+dis[j]);
	}
	tmp=0x7ffffff;
	for(int i=T; i<m+T; i++)tmp=min(tmp,dp[i]);
	return !printf("%d",tmp);
}*/

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类