类记忆化优化二维动态规划
EnofTaiPeople
·
·
题解
前情提要
数据过水导致错误 dp 只会 WA 两个点差评。
问题是我一来就认为那个错误做法很假随便 Hack 就没写。
这样的情况下还能上榜？
不过我本来就切不了这道题，因为我没想清楚，赛后还调试了两个小时才过。
### 设置状态
将 $A$ 存在数组 $a$ 中，$B$ 存在数组 $b$ 中，分别排序，设长度为 $n,m$。
容易发现同一时刻走过的火车形如 $a,b$ 中的前缀。
设 $f_{x,y}$ 表示 $a$ 中走了前 $x$ 个，$b$ 中走了前 $y$ 个，最后一次走 $A$ 这一边，出发时间为 $a_x$，之后要全部走完还需要的答案。
$g_{x,y}$ 即最后一次走 $B$ 这一边，出发时间为 $b_x$。
转移式很简单：$f_{x,y}\leftarrow f_{x+1,y}$，如果 $b_{y+1}\ge a_x+T$，可以 $f_{x,y}\leftarrow g_{x,y+1}$，$g$ 的转移同理。
### 其他转移
上面写了 $f_{x,y}\leftarrow g_{x,y+1}$ 是有条件的！
如果 $b_{y+1}<a_x+T$，下一步又想要走 $b$，该怎么办？
考虑这时会出现一次行走的末尾没有任何列车达到极限，不属于之前的任何一种状态。
发现这种情况一定形如两边交替只走 $T$ 的时间，最多不会超过 $n$ 次，所以枚举进行了多少次可以在 $O(n)$ 的时间内得出答案：
```cpp
ll sol(int tg,int x,int y,ll t){
if(x>n||y>m)return 1e18;
ll res=8e18,sum=0;
while(1){
if(x==n&&y==m){
res=min(res,sum);
break;
}
if(tg){// x ran.
while(x<n&&a[x+1]<t)sum+=t-a[++x];
if(x<n)res=min(res,sum+f[x+1][y]);
if(y==m){
if(x==n)res=min(res,sum);
break;
}
if(b[y+1]>=t+K){
res=min(res,sum+g[x][y+1]);
break;
}else tg=0,t+=K;
}else{
while(y<m&&b[y+1]<t)sum+=t-b[++y];
if(y<m)res=min(res,sum+g[x][y+1]);
if(x==n){
if(y==m)res=min(res,sum);
break;
}if(a[x+1]>=t+K){
res=min(res,sum+f[x+1][y]);
break;
}else tg=1,t+=K;
}
}
return res;
}
```
直接调用这个函数会达到 $O(n^3)$，不能通过。
但你会发现对于每一个 $x$ 都会是同一种状态，因为这时第一步 $b$ 都会走到最后一个 $b_y\le a_x+k$ 的位置，于是对于 $x$ 记忆化即可，$g$ 的转移同理。
于是做完了，时空复杂度 $O(n^2)$：
```cpp
cin>>T>>K;
while(T--){
cin>>s;
if(s[0]=='A')cin>>a[++n];
else cin>>b[++m];
}
a[++n]=0,b[++m]=0;
sort(a+1,a+n+1),sort(b+1,b+m+1);
for(i=1;i<=n;++i)A[i]=A[i-1]+a[i];
for(i=1;i<=m;++i)B[i]=B[i-1]+b[i];
for(i=0;i<=n+1;++i)
for(j=0;j<=m+1;++j)
f[i][j]=g[i][j]=3e18;
for(x=1;x<=n;++x){
for(k=1;k<=m&&b[k]<a[x]+K;++k);
tx[x]=k;
}
for(x=1;x<=m;++x){
for(k=1;k<=n&&a[k]<b[x]+K;++k);
ty[x]=k;
}
for(x=n;x;--x)
for(y=m;y;--y){
if(x==n&&y==m){
f[x][y]=g[x][y]=0;
continue;
}
f[x][y]=f[x+1][y];
if(y==tx[x]-1){
vf[x]=min(sol(0,x,tx[x]-1,a[x]+K),g[x][tx[x]]);
// cln<<x<<" "<<tx[x]<<" "<<vf[x]<<endl;
}
if(x==ty[y]-1)vg[y]=min(sol(1,ty[y]-1,y,b[y]+K),f[ty[y]][y]);
if(b[y+1]>=a[x]+K)f[x][y]=min(f[x][y],g[x][y+1]);
else{
v1=(a[x]+K)*(tx[x]-1-y)-(B[tx[x]-1]-B[y]);
// cln<<(B[tx[x]-1]-B[y-1])<<endl;
// cln<<x<<" "<<y<<" "<<v1<<endl;
f[x][y]=min(f[x][y],vf[x]+v1);
}
g[x][y]=g[x][y+1];
if(a[x+1]>=b[y]+K)g[x][y]=min(g[x][y],f[x+1][y]);
else{
v1=(b[y]+K)*(ty[y]-1-x)-(A[ty[y]-1]-A[x]);
g[x][y]=min(g[x][y],vg[y]+v1);
// cln<<(b[y]+K)*(ty[y]-1-x)<<endl;
// cln<<y<<" "<<ty[y]<<" "<<vg[y]<<endl;
}
// cln<<x<<" "<<y<<" "<<f[x][y]<<" "<<g[x][y]<<endl;
}
ll ans=min(f[1][1],g[1][1]);
printf("%lld\n",ans);
```