题目：小猿在玩一个游戏，给定一个n，代表一共有1，2，3...... n这些数字。正确的数字为其中的一个。他可以从里面任意挑选一个数字 x ，如果选错了，会知道这个数字比正确数字大了还是小了。并且消耗x个金币。他有k次机会免单，即不需要消耗金币。
求小猿要找到正确数字最少需要准备的金币。
输入：一行两个整数 n,k
示例：
输入：3 0
输出：2
第一次选择第二个数字，消耗两个金币。然后就知道正确数字在2左边还是右边，下一次一定能找到正确数字。
n,m=map(int,input().split())
cache={}
def dfs(l,r,k):
if (l,r,k) in cache:
return cache[(l,r,k)]
if k>=r-l+1&nbs***bsp;l>=r:
return 0
res=1e9
for i in range(l,r+1):
if k!=0:
res=min(max(dfs(l,i-1,k-1),dfs(i+1,r,k-1)),res)
res=min(max(dfs(l,i-1,k)+i,i+dfs(i+1,r,k)),res)
cache[(l,r,k)]=res
return res
print(dfs(1,n,m))
dfs(l,r,k)代表在l,r区间之内有k次面单机会 至少需要准备的金币数量。 过了40%超时了，不知道c++会不会超时。
全部评论
(1) 回帖