讲解 P5017 [NOIP2018 普及组] 摆渡车。

考虑动态规划算法，使用前缀和，缩小转移范围来进行优化。

思路：

考虑动态规划。

定义 \(dp_i\) 表示若有一班车在第 \(i\) 个时间出发所有人等待的时间，则状态转移方程为：

\[dp_i = dp_j + \operatorname{get}(j+1,i)(j \le i - m)

\]

其中 \(\operatorname{get}(l,r)\) 表示等车时间在 \([l,r]\) 范围内的人在 \(r\) 处上车的等待时间，考虑 \(O(1)\) 求出 \(\operatorname{get}(l,r)\)。

定义 \(s_i\) 表示等车时间在 \([0,i]\) 的所有人的等车时间之和，\(a_i\) 表示等车时间在 \([0,i]\) 的人的个数，则：

\[\operatorname{get}(l,r) = r \times (a_r - a_{l-1}) - (s_r - s_{l-1})

\]

此时时间复杂度优化到了 \(O(T^2)\)，考虑缩小 \(j\) 的范围。

注意到若在某时刻回来，且等待不发车时间 \(>m\) 了，肯定没有中间发一次车优，则 \(j\) 的范围应该在 \([i-2m,i-m]\)。

此时时间复杂度为 \(O(TM)\)。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=4e6+10;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll n,m,x,k,ans=1e18;

ll a[N],s[N],dp[N];

ll get(ll l,ll r){

if(l>r)

return 0;

if(!l)

return r*a[r]-s[r];

return r*(a[r]-a[l-1])-(s[r]-s[l-1]);

}

bool End;

int main(){

memset(dp,0x7f,sizeof(dp));

n=read(),m=read();

while(n--){

x=read();

a[x]++;

k=max(k,x);

}

for(ll i=1;i<N;i++){

s[i]=s[i-1]+a[i]*i;

a[i]+=a[i-1];

}

for(int i=0;i<m;i++)

dp[i]=get(0,i);

for(int i=m;i<=k+m;i++)

for(int j=max(0ll,i-2ll*m);j<=i-m;j++)

dp[i]=min(dp[i],dp[j]+get(j+1,i));

for(int i=k;i<=k+m;i++)

ans=min(ans,dp[i]);

write(ans);

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}