网站首页
编程语言
数据库
系统相关
其他分享
编程问答
ABC177F
2024-07-09
Solution - Atcoder ABC177F I hate Shortest Path Problem
考虑按题目所述的进行DP。设计状态\(f_{i,j}\)代表强制要求\((i,j)\)要走向\((i+1,j)\)最小的横坐标之差,这是因为对应的纵坐标之差是确定的。对于转移,考虑到对于\(j\not\in[a_i,b_i]\),直接从上面转移下来即可,即\(f_{i,j}\leftarrowf_{i-1,j}\)。对于\(j