题意：
时间轴上分布着$n$位乘客（$1\le n\le 500$），$i$号乘客的位置为$t_i$（0\le t_i\le 4\times 10^6），用互相距离不小于$m$的车次将时间轴分为若干部分，并管辖以自己为右端点的这个区间（除了第一趟车包括$0$，其他车次左开右闭），求最小费用和。每个车次的费用来自：管辖区间内所有乘客与该车次的距离之和。
程序1（30pts）：
考虑DP。
设在$i$时刻等车的人共有$c_i$位，再设在$i$时刻发车的费用以及之前所有车次费用之和的最小值为$f_i$。
①若这是第一趟车，则累加$i$时刻之前所有人等车的时间：
$$f_i=\sum\limits_{j=0}^{i} c_j\times(i-j)$$
②若非第一趟车，则枚举上一趟车发车的时间$j$，再累加$j+1$到$i$时刻的人等车的时间：
$$f_i=\mathop{min}\limits_{0\le j\le i-m}\{f_j+\sum\limits_{k=j+1}^i c_k\times(i-k)\}$$
考虑最终答案怎么算。假设最后一名乘客的位置为$T$，则最后一趟车次时间必在$[\,T,T+m\,)$中，取这些时间的$f_i$最小值即可。
DP做完了。然而时间复杂度为$O(T^3)$，只有$30$分。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //设在i时刻等车的人共有c_i位 int f[T + M + 3]; //设在i时刻发车的费用以及之前所有车次费用之和的最小值为f_i //时间轴会用到T+m，对应的数组的范围也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //统计c[]时刻等车的人的个数 maxt = max(maxt, t[i]); } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟车最晚在maxt+m-1时发出 int tmp = 0; for(int j = 0; j <= i; j++) tmp += c[j] * (i - j); f[i] = tmp; //初值：如果此时发第一趟车的费用 for(int j = 0; j <= i - m; j++){ //如果上一趟车是j时刻发的 tmp = 0; for(int k = j + 1; k <= i; k++) //累加j+1~i时刻等车的人 tmp += c[k] * (i - k); f[i] = min(f[i], f[j] + tmp); //取最小值 } } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟车的时间可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
程序2（50pts）：
发现式子里有很多连续区间的运算，尝试变形一下式子以便使用前缀和优化。
$$\sum\limits_{j=0}^{i} c_j\times(i-j)=i\sum\limits_{j=0}^i c_j - \sum\limits_{j=0}^i j\times c_j$$
设$c_i$的前缀和为$C_i$，$i\times c_i$的前缀和为$S_i$，则原式
$$=i\times C_i - S_i$$
再看
$$\begin{matrix}\sum\limits_{k=j+1}^i c_k(i-k)&=i\sum\limits_{k=j+1}^i c_k-\sum\limits_{k=j+1}^i k\times c_k\\&=i(C_i-C_j)-(S_i-S_j)\end{matrix}$$
于是我们就可以$O(1)$转移了，整体时间复杂度下降到$O(T^2)$，可以得到$50$分。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //设在i时刻等车的人共有c_i位 int C[T + M + 3], S[T + M + 3]; //c_i前缀和；i*c_i前缀和 int f[T + M + 3]; //设在i时刻发车的费用以及之前所有车次费用之和的最小值为f_i //时间轴会用到T+m，对应的数组的范围也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //统计c[]时刻等车的人的个数 maxt = max(maxt, t[i]); } C[0] = c[0]; S[0] = 0; for(int i = 1; i <= maxt + m; i++){ C[i] = C[i - 1] + c[i]; S[i] = S[i - 1] + i * c[i]; } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟车最晚在maxt+m-1时发出 f[i] = i * C[i]-S[i]; //初值：如果此时发第一趟车的费用 for(int j = 0; j <= i - m; j++) //如果上一趟车是j时刻发的 f[i] = min(f[i], f[j] + i * (C[i] - C[j]) - (S[i] - S[j])); } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟车的时间可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
程序3（70pts）：
DP转移是枚举上一步，而这个DP里每个状态都从$0$状态开始枚举上一步，显然有很多冗余，需要剪去无用转移。
思考一下，发现我们不会切出一个长度$\ge 2m$的区间出来，因为这样的区间至少可以多切一次，得到两个长度$\ge m$的区间，总费用可能减少或者不变。
于是乎，若不是第一趟车，则
$$f_i=\mathop{min}\limits_{i-2m<j\le i-m}\{f_j+i(C_i-C_j)-(S_i-S_j)\}$$
现在我们的DP时间复杂度为$O(T\times m)$，理论得分$70$分。
（洛谷用了比较好的评测机，我这发差不多$1e9$的运算也A了）
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //设在i时刻等车的人共有c_i位 int C[T + M + 3], S[T + M + 3]; //c_i前缀和；i*c_i前缀和 int f[T + M + 3]; //设在i时刻发车的费用以及之前所有车次费用之和的最小值为f_i //时间轴会用到T+m，对应的数组的范围也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //统计c[]时刻等车的人的个数 maxt = max(maxt, t[i]); } C[0] = c[0]; S[0] = 0; for(int i = 1; i <= maxt + m; i++){ C[i] = C[i - 1] + c[i]; S[i] = S[i - 1] + i * c[i]; } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟车最晚在maxt+m-1时发出 f[i] = i * C[i]-S[i]; //初值：如果此时发第一趟车的费用 for(int j = max(0, i - m * 2 + 1); j <= i - m; j++) //如果上一趟车是j时刻发的 //注意j不能为负数 f[i] = min(f[i], f[j] + i * (C[i] - C[j]) - (S[i] - S[j])); } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟车的时间可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
程序4（100pts）：
看起来转移已经很简洁了，但是算法的复杂度仍没有达到要求。
思考一下，发现我们尝试对每个时间位置($0\sim T+m$，约$4\times 10^6$)都算了一遍转移，也就是尝试在这个位置发了一辆车（由$f$的定义），但实际上有效发车的时间位置一定不会超过$n\times m$个（约$5\times 10^4$），我们可以剪去无用状态。
换句话说，对于在$t_i$位置等车的人，接走他的车的时间位置一定在$[t_i,t_i+m)$范围内。
再换句话说，如果时间轴上有一段长度不少于$m$的区间没有任何乘客，那么我们在这个区间右端发不发车费用都一定不会增加，可以直接继承状态，即
$$f_i\leftarrow f_{i-m},\qquad C_i=C_{i-m}$$
算算时间复杂度，只在有效发车时间位置做转移，所以总时间复杂度是$O(T+n\times m^2)$，可以得到满分。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //设在i时刻等车的人共有c_i位 int C[T + M + 3], S[T + M + 3]; //c_i前缀和；i*c_i前缀和 int f[T + M + 3]; //设在i时刻发车的费用以及之前所有车次费用之和的最小值为f_i //时间轴会用到T+m，对应的数组的范围也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //统计c[]时刻等车的人的个数 maxt = max(maxt, t[i]); } C[0] = c[0]; S[0] = 0; for(int i = 1; i <= maxt + m; i++){ C[i] = C[i - 1] + c[i]; S[i] = S[i - 1] + i * c[i]; } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟车最晚在maxt+m-1时发出 if(i >= m && C[i] == C[i - m]){ //如果在i发车接不到任何人 f[i] = f[i - m]; //直接继承状态，费用不会变化 continue; } f[i] = i * C[i]-S[i]; //初值：如果此时发第一趟车的费用 for(int j = max(0, i - m * 2 + 1); j <= i - m; j++) //如果上一趟车是j时刻发的 //注意j不能为负数 f[i] = min(f[i], f[j] + i * (C[i] - C[j]) - (S[i] - S[j])); } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟车的时间可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
小结：
掌握DP的基础优化方法：前缀和优化、剪去无用转移、剪去无用状态，做到不写脑残的DP。