题解 P5017 【摆渡车】

## 此题做法：DP！ 首先将t数组升序排序 **设f[i][j]表示第i个人等了j分钟的车，载完前i个人的最小等车时间总和。** j的取值范围？ 由题可知，若车在人大附中停了m分钟，那么不如在到人大附中时先送走一批人（即便当时没人），所以停车时间T1<m 设一个人等到车从人民大学回来的时间为T2 因为车往返一次只需m分钟，所以T2<m 综上，一个人等车的时间 **j=T1+T2<2m** 该如何转移？ 1. 若下一个人能赶上当次车（即t[i]+j>=t[i+1]), 则将f[i][j]+t[i]+j-t[i+1]转移至f[i+1][t[i]+j-t[i+1]]; 2. 若下一个人在当次车回来之前开始等车（即t[i]+j+m>=t[i+1])， 则枚举车回来后停的时间k, 用f[i][j]+t[i]+j+m+k-t[i+1]转移f[i+1][t[i]+j+m+k-t[i+1]]; 3. 若下一个人在当次车回来之后才到（即t[i]+j+m<t[i+1]),则枚举下 一个人等待的时间k，并用f[i][j]+k转移f[i+1][k]; 空间复杂度O(nm),时间复杂度O(nm^2),~~正确性显然~~ 附AC代码 ```cpp #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,m,mi,a[510]; typedef long long ll; ll f[510][210],ans; void min(ll &x,ll y) { y < x && (x = y); } int main() { scanf("%d%d",&n,&m); for(int i = 1;i <= n; ++ i) scanf("%d",a + i), mi = mi < a[i] ? mi : a[i]; for(int i = 1;i <= n; ++ i) a[i] -= mi; sort(a + 1,a + n + 1); memset(f,0x3f,sizeof f); for(int i = 0;i < 2 * m; ++ i) f[1][i] = i; for(int i = 1;i < n; ++ i) for(int j = 0;j < 2 * m; ++ j) if(f[i][j] < 0x3f3f3f3f3f3f3f3f) { if(a[i] + j >= a[i + 1]) min(f[i + 1][a[i] + j - a[i + 1]],f[i][j] + a[i] + j - a[i + 1]); for(int k = a[i] + j + m >= a[i + 1] ? 0 : a[i + 1] - a[i] - j - m;a[i] + j + m + k - a[i + 1] < m * 2; ++ k) if(a[i] + j + m + k >= a[i + 1]) min(f[i + 1][a[i] + j + m + k - a[i + 1]],f[i][j] + a[i] + j + m + k - a[i + 1]); if(a[i] + j + m < a[i + 1]) for(int k = 0;k < m * 2; ++ k) min(f[i + 1][k],f[i][j] + k); } ans = 0x3f3f3f3f3f3f3f3f; for(int i = 0;i < m * 2; ++ i) min(ans,f[n][i]); printf("%lld\n",ans); return 0; } ```