好久没有做题了..刷刷DP吧,之前都没有好好做过这方面的题,比赛一遇到就放过..没有一点思路.
这是个比较基础的,还好是我自己想出来的,没有看hints.对于每对猜测次数G和生命值L,需要得到一个最大的N,让其可以找到一个策略,能在G和L都没用完前猜出正确的数,即必胜策略. 我们平时玩这种游戏的时候都是二分..然后从经验上判断这个是最快能猜到那个数的.这里因为有生命值,所以复杂了些.我们假设这个某对GL对应的最大的N为nmax,第一步我们的必胜策略肯定是从中间找一个数k,然后判断这个数是大了还是小了还是刚好. 如果没有猜中,就从左边或者右边的范围内继续查找.假设dp[i][j]表示当猜测次数是i,生命值是j的时候能得到的最大的N.
再来看k,如果k猜大了,那么生命值就减少了1.需要从小于k的范围内再猜,在小于k的范围内所能得到的最大N是dp[i-1][j-1],在大于k的范围内的到最大N是dp[i-1][j],所以可得dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1,这就是状态转移方程.
又开始做题了？
没有，我就是随便刷刷题。。