状态压缩

状态压缩DP

写dp的时候方程中最重要的就是表示状态了。比如说做01背包时,\(dp[i][j]\)表示放第\(i\)个物品的时候容量为\(j\)时的最大价值。这里\(i\)、\(j\)就是状态。
但是有的时候,所需要表示的状态太多,很容易会使空间复杂度爆炸,这时候就需要适当的压缩状态的表示。

tyvj 1059 过河
首先这题很容易想到\(dp[i]=min(dp[i-j])\)的dp。
然而1e9的n,无论是空间还是时间都是爆炸。
其实细想一下,因为石头的个数有限,所以\(dp[i]\)会出现大量的相同状态,这些状态有的对转移根本没有作用。事实上,可以将这些成段的给省略掉。

压缩的根据如下,因为S到T之间都能取,当S=s*(s+1),取特解x=x’+(S+1)*t, y=y’-S*t
会发现x和y总有非负整数解,每次Q加1就相当于少取一个S多取一个(S+1),遇到Q的整数倍表现出周期性。观察到在这种情况下S不大于9,T不大于10。
这样,对于某块石头,如果它后面紧跟着那块石头与它相距超过90,我们可以将从后一块石头开始的所有石头往前移动直到最近的那块与它的距离是90而不改变规划结果。

如果不了解这个压缩方法,其实可以通过预处理与石子有关的格子,然后仅仅对这些格子进行dp就行了。

Continue reading