大概是 2018 年的翻译,然后这个翻译让我对一个错题搞了半个早上
正确翻译:
有 n 种物品和一个大小为 k 的队列,有 pi 的概率会选择第 i 种物品放入队列,如果队列已经有 i 则将队列中的 i 移到队尾 。
对着这个假题意做了很久,怎么看这个东西直接做 dp 都不对,于是看了几篇题解还是觉得有锅,即使倒着考虑这个问题,例如类似 duyi 博客中的这个序列 5 2 1 5 3 4
,如果直接倒着做会发现第二个 5 并不在当前集合中,但是却不能往集合里面加入 5 ,因为按照题意来正着做会让 5 本身存在于队列中的,也就是说序列上前面的数会对后面造成影响。
但是如果用正确题意来做,会发现它前面是否存在 5 并不影响这个位置把 5 放到队尾,所以只需要反着考虑,就不会产生前面对后面的影响,就可以变成题解中说的问题(即如果选到当前选择过的数就不管,继续操作下去,选择到新的数直接加入序列)
感觉可能主要是除了 duyi 的题解都缺少理性说明(但是duyi的题解好像也忽略了这种情况),导致这个错翻译一直未被修正。。