"NOI2005"瑰丽华尔兹
题目链接
<h1>题目大意</h1>
现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动(上下左右),当然每个时间点可以选择让钢琴不动,不允许钢琴超出边界或者碰到障碍,询问钢琴可能走的最远距离是多少.
其中 $1 \leq n,m \leq 200$,区间个数 $k \leq 200$,区间最大的右端点 $ T \leq 40000$
<h1>题解</h1>
首先对于这个题目我们有一个很朴素的暴力,也就是记 $f_{i,x,y}$ 表示在时间点