[DP] [LuoguP1282] 多米诺骨牌

题目传送门 这题属于补坑题，原来交的Pascal…… 对于一对骨牌，可以发现要么翻要么不翻，翻转一次对总体差值的影响为2c$2c$，其中c$c$为这对骨牌的差值。 证明如下： 不管绝对值问题。设这对骨牌点数分别为x$x$，y$y$，与x$x$一行的骨牌（除了x$x$）的点数和为p$p$，与y$y$一行的骨牌（除了y$y$）的点数和为q$q$。 原来的差值为x+p−y−q$x+p-y-q$，交换后为y+p−x−q$y+p-x-q$。 则差值的变化δ=(y+p−x−q)−(x+p−y−q)=2y−2x=2c$/delta=(y+p-x-q)-(x+p-y-q)=2y-2x=2c$，证毕。 所以，一对骨牌的翻转对于其他骨牌没有影响，只与自己状态有关，所以转化为01背包问题，背包容量即为骨牌的差值。因为这里差值有正有负，所以将零点定为5n$5n$即可。 DP方程式为： dp[j]=min(dp[j+2ci])+1     j∈[−5n,5n] $$/begin{equation}dp[j]=min(dp[j+2c_i])+1/ / / / / j/in [-5n,5n]/end{equation}$$ 初值为 dp[i]={0    i=sum+∞   i≠sum $$/begin{equation}dp[i]=/begin{cases}0/ / / / i=sum//+/infty / / / i /not= sum/end{cases}/end{equation}$$ 其中，sum$sum$为初始骨牌点数差的和。 答案为从零点向两边扫到的第一个非最大值的较小值。 时间复杂度O(n2)$O(n^2)$，需要注意枚举顺序（01背包的注意问题了……） Code