ZOJ 1503 One Person “The Price is Right”

于 2012年06月6日 发布在 算法&&ACM 跳到评论

好久没有做题了..刷刷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,这就是状态转移方程.

本文共有 2条评论 | 沙发:文章评论

  1. 匿名说道:

    又开始做题了?

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)