Solution

我的做法转移就是 $O(1)$ 而不是均摊 $O(1)$ 的，还比较好写，跑得快。

显然要将两个车站的列车划分为若干连续段，两个连续段交错排列。

考虑这样一个 DP：设 $dp_{i,j,t,0/1}$ 表示，当前期限是时间 $t$，两个车站分别走了 $i$ 和 $j$ 个人，最后一个添加的连续段是 $\rm A$ 还是 $\rm B$ 车站。

注意到 $t$ 一定是某个人卡到上界之后，不断按照 $+T$ 的形式得出的，所以 $t$ 可以写为 $t_x + yT$ 的形式，所以得到 $dp_{i,j,x,y,0/1}$。

注意到当 $x$ 给定，最优结构的形态就相对确定了——使用归纳法可以的得知（真的假的，感性理解是这样的），最小的 $y$ 一定对应最小的 $dp_{i,j,x,y}$。所以可以把 $y$ 扔进状态里面。所以状态只剩下 $dp_{i,j,x,0/1}$。

而 $x$ 显然要么是 $i$ 对应 $\rm A$ 的位置要么是 $j$ 对应的 $\rm B$ 的位置，所以可以变为 $dp_{i,j,0/1,0/1}$。

直接把你的 $O(n^4)$ 暴力往上套即可。复杂度 $O(n^2)$。

为啥题解区都没有这个解法啊？？

#include<bits/stdc++.h>
#define ll long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5000+10;
int n,tp[MAXN];
ll T,t[MAXN],t0[MAXN],t1[MAXN];
pair<ll,ll> dp[2][MAXN][2][2];
pair<ll,ll> operator +(pair<ll,ll> A,pair<ll,ll> B) {return {A.first+B.first,A.second+B.second};}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>T;
	ffor(i,1,n) {char ch;cin>>ch>>t[i],tp[i]=ch-'A';}
	memset(dp,0x3f,sizeof(dp));
	int c0=0,c1=0;
	ffor(i,1,n) if(tp[i]==0) t0[++c0]=t[i]; else t1[++c1]=t[i];
	sort(t0+1,t0+c0+1),sort(t1+1,t1+c1+1);
	ffor(i,0,c0) {
		int s=i&1,l=s^1;
		memset(dp[s],0x3f,sizeof(dp[s]));
		if(i==0) dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][1][0]=dp[0][0][1][1]={0,T};
		ffor(j,0,c1) {
			if(i) {
				ffor(o,0,1) {
					auto nw=dp[l][j][o][0];
					if(nw.second-T>=t0[i]) dp[s][j][o][0]=min(dp[s][j][o][0],nw+make_pair(nw.second-T-t0[i],0));
					else dp[s][j][0][0]=min(dp[s][j][0][0],nw+make_pair(0,t0[i]+T-nw.second));
					nw=dp[l][j][o][1];
					if(nw.second>=t0[i]) dp[s][j][o][0]=min(dp[s][j][o][0],nw+make_pair(nw.second-t0[i],T));
					else dp[s][j][0][0]=min(dp[s][j][0][0],nw+make_pair(0,t0[i]+T-nw.second));
				}
			}
			if(j) {
				ffor(o,0,1) {
					auto nw=dp[s][j-1][o][1];
					if(nw.second-T>=t1[j]) dp[s][j][o][1]=min(dp[s][j][o][1],nw+make_pair(nw.second-T-t1[j],0));
					else dp[s][j][1][1]=min(dp[s][j][1][1],nw+make_pair(0,t1[j]+T-nw.second));
					nw=dp[s][j-1][o][0];
					if(nw.second>=t1[j]) dp[s][j][o][1]=min(dp[s][j][o][1],nw+make_pair(nw.second-t1[j],T));
					else dp[s][j][1][1]=min(dp[s][j][1][1],nw+make_pair(0,t1[j]+T-nw.second));
				}
			}
		}
	}
	ll ans=LONG_LONG_MAX;
	ffor(o1,0,1) ffor(o2,0,1) ans=min(ans,dp[c0&1][c1][o1][o2].first);
	cout<<ans;
	return 0;
}