题意：
时间轴上分布着$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;
}
程序1（30pts）
程序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;
}
程序2（50pts）
程序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;
}
程序3（70pts）
程序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;
}
程序4（100pts）
小结：
掌握DP的基础优化方法：前缀和优化、剪去无用转移、剪去无用状态，做到不写脑残的DP。
标签：const,limits,int,题解,2023.10,T3,times,发车,include From： https://www.cnblogs.com/Hansue/p/17770061.html