定义 $dp_{k,i}$ 表示恰好观看了 $k$ 部电影，且最后一部观看的是第 $i$ 部电影时，所花费的最小总时间‌。若不可达，则 $dp_{k,i}\gets\infin$。

当只观看 $1$ 部电影时，没有路途消耗，只需支付播放时间：

$$dp_{1,i}\gets⁡t_i$$

其他状态初始不可达：

$$dp_{i,j}\gets\infin(2\le⁡i\le⁡N)$$

对于 $dp_{k,i}$，枚举第 $k−1$ 部电影的下标 $j(1\le⁡j<i)$。$dp_{k,i}$ 可分为以下几部分：

• 观看前 $k-1$ 部电影的时间 $dp_{k-1,j}$。
• 从电影院 $p_j$ 到 $p_i$ 的时间 $|p_i-p_j|$。
• 看电影 $i$ 的时间 $t_i$。

因此转移方程如下：

$$dp_{k,i}\gets\min_{1\le⁡j<i}\{dp_{k−1,j}+t_i+|p_i−p_j|\}$$

从小到大枚举观看电影的数量 $k$。对于每个 $k$，检查是否存在某个 $i$ 使得 $dp_{k,i}\le T$。如果存在，说明可行，更新答案 $ans\gets⁡k$。

如果对于某个 $k$，所有的 $dp_{k,i}$ 都大于 $T$，则无法观看 $k$ 部电影，可以直接跳出循环。