P6879 スタンプラリー 3 题解

发布时间 2023-08-10 19:05:17作者: Mo默Sh笙

思路前几篇题解都介绍了,这里着重介绍一个状态设计的小技巧。

在设计状态时,我们可能会碰到状态数值过大,而dp数组内存的值较小的情况。

例如在该题用 \(dp_{l,r,t,0/1}\) 表示逆时针经过 \(l\) 个,顺时针经过 \(r\) 个,已经花费 \(t\) 秒,所拿到的雕像个数,\(0\) 表示当前在左端点,\(1\) 表示在右端点。

但是 \(T_{i}\leq10^9\),这样设计显然会爆空间。

注意到 \(N\leq200\),我们可以将状态和数组所存值互换,用 \(dp_{l,r,k,0/1}\) 表示拿 \(k\) 个雕像所花费的时间,解决了状态数值爆空间的问题。