题目大意&题解
现在取款机里最多有存款k,现在我们不知道取款机里的剩余钱数(但是我们知道剩余钱数的上界),我们每次可以尝试着取钱,如果取的钱大于取款机里的钱数取款机就会警告,如果被警告w次就会被警察带走…问采取最优策略时的期望取款次数。
一开始完全想错了,本来想的是用二分的方法去取钱…(二进制),然而发现第三组样例是错的,感觉是思路有问题。后来查了下题解说是用DP…瞬间就懂了…
我们设\(E(i,j) \)是上界为i时,还可以被警告j次的最优解,那么通过枚举剩余钱数,很好写出转移: \[ E(i,j)=( \sum_{k=1}^n(\frac{i-k+1}{i+1}·E(i-k,j)+\frac{k}{i+1}·E(i-1,k-1)+1 ) )_{min} \]