题解 P1777 帮助_NOI导刊2010提高

· · 题解

嗯。。

这道题倒是一道蛮好的简单状压DP。。

我们可以设状态f[i][j][k][l]表示考虑第i本书的时候已经选出了j本书需要取出来，之前存在的书的集合为k，最后一本没有取出来的书的编号为l。那么这样的话转移方程也比较显然了。

若不将这本书取出来:

f[i][j][k\ |\ h_i][h_i]\ =\ min(f[i][j][k\ |\ h_i][h_i],\ f[i-1][j][k][l]\ +\ (l\ ==\ h_i\ ?\ 0\ :\ 1))

若将这本书取出来:

f[i][j + 1][k][l]\ =\ min(f[i][j + 1][k][l],\ f[i-1][j][k][l])

直接这么爆搞就行了。。

最后的答案的话。。

首先枚举j,\ k,\ l。若我们设最后的答案为res，那么我们就要按照这样更新它:

res = min(res,\ f[n][j][k][l] + Calc(k\ xor\ S))

其中Calc是计算给出的二进制数中含1的位数，S表示输入中所含的书的集合。

这里Calc的意义在于: 之前取出来的书中有些高度是前面没有的，所以我们把它取出来后再放进去仍然有1的贡献，所以我们需要加上它的贡献。

最后算出来的res就是答案了。

完美结束

P.s. 好像不能直接开这么大的数组，空间会爆掉，需要用循环利用。