问题描述

我们需要为单人版"价格猜猜看"游戏设计一个策略分析算法。给定G次猜测机会和L条生命线，计算能确保猜中1到N范围内任意价格的最大N值。

游戏规则

1. 每次猜测后有三种结果：
   • 正确：获胜
   • 过低：消耗1次猜测机会
   • 过高：消耗1次猜测机会和1条生命线
2. 失败条件：
   • 用尽所有猜测机会
   • 猜测过高时没有剩余生命线

目标

对于给定的G和L，找到最大的N，使得存在一种策略能确保猜中1到N之间的任何价格。

解题思路

这个问题可以使用动态规划来解决。我们定义dp[g][l]为使用g次猜测机会和l条生命线时能覆盖的最大价格范围。

状态转移

对于当前状态dp[g][l]，我们选择一个猜测点k：

1. 如果猜测正确：直接获胜
2. 如果猜测过高：
   • 消耗1次猜测和1条生命线
   • 实际价格在1到k-1之间
3. 如果猜测过低：
   • 消耗1次猜测
   • 实际价格在k+1到N之间

因此状态转移方程为： dp[g][l] = dp[g-1][l] (过低情况) + 1 (正确情况) + dp[g-1][l-1] (过高情况)

边界条件

1. dp[0][l] = 0 (没有猜测机会)
2. dp[g][0] = g (没有生命线，只能从低到高猜测)

代码解释

1. 预处理函数precompute()：

   • 初始化边界条件
   • 使用动态规划填充dp表

2. 主函数main()：

   • 调用预处理函数
   • 读取输入并输出结果
   • 处理多个测试用例直到遇到G=L=0

3. 动态规划表dp：

   • dp[g][l]表示用g次猜测和l条生命线能覆盖的最大价格范围
   • 通过状态转移方程计算每个状态的值