ZJU/ZOJ 1503 One Person "The Price is Right" 解题报告

题目大意是一个人有g次猜数机会和l条生命线，每次猜数如果猜错了则扣除一次猜数机会，如果猜高了还要扣除一条生命线，如果在没有生命线的情况下猜高了就输了。问在有g次猜数机会和l条生命线的情况下最多能保证正确猜出多少以内的数？

用f[i,j]表示g=i,l=j的情况下可以保证猜中的最大数，将每次猜数分成三种情况，猜低、猜中和猜高，则可推出状态转移方程f[i,j]=f[i-1,j]+1+f[i-1,j-1];由于l=0的情况下只能猜低的数，因此初始化f[i,0]=i;

1651819    2008-09-29 22:39:48     Accepted    1503    FPC    0    116    IwfWcf