网站首页
编程语言
数据库
系统相关
其他分享
编程问答
ABC265F
2024-07-27
ABC265F 题解
题面\(O(nd^2)\)考虑\(f(i,j,k)\)表示dp到第\(i\)维,距离\(p,q\)曼哈顿距离\(j,k\)的方案数。考虑朴素转移:设\(dis=|p_{i+1}-q_{i+1}|\)。\[\begin{aligned}f(i+1,j+t,k+dis-t)&\getsf(i,j,k)&(0\leqt\leqdis)\quad&(1)\\f(i+1,j+d+t,k+t)&\ge