2 条题解
-
0
自动搬运
来自洛谷，原作者为
CYJian
今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました搬运于
2025-08-24 21:30:14，当前版本为作者最后更新于2018-05-28 22:37:11，作者可能在搬运后再次修改，您可在原文处查看最新版自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多
以下是正文
嗯。。
这道题倒是一道蛮好的
简单状压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])$
直接这么爆搞就行了。。
最后的答案的话。。
首先枚举。若我们设最后的答案为，那么我们就要按照这样更新它:
其中是计算给出的二进制数中含1的位数，表示输入中所含的书的集合。
这里的意义在于: 之前取出来的书中有些高度是前面没有的，所以我们把它取出来后再放进去仍然有的贡献，所以我们需要加上它的贡献。
最后算出来的就是答案了。
完美结束P.s. 好像不能直接开这么大的数组，空间会爆掉，需要用循环利用。
-
0
15011418730
LV 7
@ 2025-8-24 21:28:59
自动搬运
来自洛谷，原作者为
CYJian
今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました搬运于
2025-08-24 21:28:59，当前版本为作者最后更新于2018-05-28 22:37:11，作者可能在搬运后再次修改，您可在原文处查看最新版自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多
以下是正文
嗯。。
这道题倒是一道蛮好的
简单状压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])$
直接这么爆搞就行了。。
最后的答案的话。。
首先枚举。若我们设最后的答案为，那么我们就要按照这样更新它:
其中是计算给出的二进制数中含1的位数，表示输入中所含的书的集合。
这里的意义在于: 之前取出来的书中有些高度是前面没有的，所以我们把它取出来后再放进去仍然有的贡献，所以我们需要加上它的贡献。
最后算出来的就是答案了。
完美结束P.s. 好像不能直接开这么大的数组，空间会爆掉，需要用循环利用。
- 1
