潜江市网站建设_网站建设公司_百度智能云_seo优化

题目描述

Alice \texttt{Alice}Alice和Bob \texttt{Bob}Bob设计了一个双人猜数游戏。游戏开始前，他们约定两个正整数：范围N NN和允许的失误次数上限S SS。Alice \texttt{Alice}Alice秘密选择一个整数X XX（0 ≤ X < N 0 \le X < N0≤X<N），然后Bob \texttt{Bob}Bob轮流猜测整数。对于Bob \texttt{Bob}Bob的每次猜测，Alice \texttt{Alice}Alice会给出以下三种回应之一：

• strike \texttt{strike}strike：如果猜测的数字大于X XX；
• smile \texttt{smile}smile：如果猜测的数字小于X XX；
• stop \texttt{stop}stop：如果猜测的数字等于X XX（此时游戏结束，Bob \texttt{Bob}Bob获胜）。

如果Bob \texttt{Bob}Bob累计收到S SS次strike \texttt{strike}strike，则游戏结束，Alice \texttt{Alice}Alice获胜。

Bob \texttt{Bob}Bob希望在正式比赛前进行训练。他需要知道，对于给定的N NN和S SS，在最坏情况下，他需要多少次猜测才能确保猜中Alice \texttt{Alice}Alice选择的任意数字X XX，并且在此过程中他最多收到S − 1 S-1S−1次strike \texttt{strike}strike（否则他会输掉游戏）。

输入格式：第一行包含一个整数C CC，表示测试用例的数量。接下来C CC行，每行包含两个整数N NN和S SS，分别表示数字范围和允许的strike \texttt{strike}strike次数上限。保证1 ≤ N ≤ 1000 1 \le N \le 10001≤N≤1000，1 ≤ S ≤ 20 1 \le S \le 201≤S≤20。

输出格式：对于每个测试用例，输出一行一个整数，表示Bob \texttt{Bob}Bob在最坏情况下所需的最少猜测次数。

题目分析

这是一个典型的最坏情况下的最优策略问题，类似于带有限制的二分搜索。我们可以从以下几个关键点理解题目：

1. 游戏目标：Bob \texttt{Bob}Bob需要保证无论Alice \texttt{Alice}Alice选择哪个数字X XX，他都能在收到少于S SS次strike \texttt{strike}strike的情况下猜中。
2. 策略限制：每次猜测如果得到strike \texttt{strike}strike，会消耗一次“允许的失误机会”；如果得到smile \texttt{smile}smile，则不消耗。
3. 最坏情况：我们需要考虑在所有可能的X XX下，Bob \texttt{Bob}Bob所需猜测次数的最大值，并最小化这个最大值。

解题思路

1. 问题建模

设d p [ n ] [ s ] dp[n][s]dp[n][s]表示当数字范围为[ 0 , n − 1 ] [0, n-1][0,n−1]（即共有n nn个可能的数字），且Bob \texttt{Bob}Bob最多还能承受s ss次strike \texttt{strike}strike时，在最坏情况下需要的最少猜测次数。

初始条件：

• 如果没有数字需要猜（n = 0 n = 0n=0），则不需要猜测：d p [ 0 ] [ s ] = 0 dp[0][s] = 0dp[0][s]=0。
• 如果不能承受任何strike \texttt{strike}strike（s = 0 s = 0s=0），那么Bob \texttt{Bob}Bob只能从最小的数字开始逐个猜测，最坏情况需要猜n nn次（当X = n − 1 X = n-1X=n−1时）：d p [ n ] [ 0 ] = n dp[n][0] = ndp[n][0]=n。

状态转移：

假设当前范围大小为n nn，我们选择猜测位置k kk（0 ≤ k < n 0 \le k < n0≤k<n）。猜测后有三种可能：

1. 猜中：游戏结束，本次猜测计数为1 11。
2. 得到strike \texttt{strike}strike（猜大了）：说明X < k X < kX<k，剩余范围大小为k kk，剩余可承受strike \texttt{strike}strike次数为s − 1 s-1s−1，后续需要的最少猜测次数为d p [ k ] [ s − 1 ] dp[k][s-1]dp[k][s−1]。
3. 得到smile \texttt{smile}smile（猜小了）：说明X > k X > kX>k，剩余范围大小为n − k − 1 n-k-1n−k−1，剩余可承受strike \texttt{strike}strike次数仍为s ss，后续需要的最少猜测次数为d p [ n − k − 1 ] [ s ] dp[n-k-1][s]dp[n−k−1][s]。

由于我们要保证最坏情况，所以对于固定的k kk，需要的猜测次数为：
guesses ( k ) = 1 + max ⁡ ( d p [ k ] [ s − 1 ] , d p [ n − k − 1 ] [ s ] ) \texttt{guesses}(k) = 1 + \max(dp[k][s-1],\ dp[n-k-1][s])guesses(k)=1+max(dp[k][s−1],dp[n−k−1][s])
其中1 11表示当前这次猜测。

为了最小化最坏情况，我们选择最优的k kk：
d p [ n ] [ s ] = min ⁡ k = 0 n − 1 ( 1 + max ⁡ ( d p [ k ] [ s − 1 ] , d p [ n − k − 1 ] [ s ] ) ) dp[n][s] = \min_{k=0}^{n-1} \left(1 + \max(dp[k][s-1],\ dp[n-k-1][s])\right)dp[n][s]=k=0minn−1​(1+max(dp[k][s−1],dp[n−k−1][s]))

2. 算法实现

由于N ≤ 1000 N \le 1000N≤1000，S ≤ 20 S \le 20S≤20，我们可以使用动态规划预先计算所有可能的d p [ n ] [ s ] dp[n][s]dp[n][s]值。对于每个测试用例，直接查表输出结果即可。

• 时间复杂度：O ( N 2 ⋅ S ) O(N^2 \cdot S)O(N2⋅S)，对于给定范围是可接受的。
• 空间复杂度：O ( N ⋅ S ) O(N \cdot S)O(N⋅S)。

3. 注意事项

• 题目中给出的S SS是Alice \texttt{Alice}Alice获胜所需的strike \texttt{strike}strike次数，因此Bob \texttt{Bob}Bob最多能承受S − 1 S-1S−1次strike \texttt{strike}strike。我们在计算时实际使用的s = S − 1 s = S-1s=S−1。
• 当S = 1 S = 1S=1时，Bob \texttt{Bob}Bob不能承受任何strike \texttt{strike}strike（s = 0 s=0s=0），此时只能顺序猜测，需要N NN次。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=1005;constintMAX_S=25;constintINF=0x3f3f3f3f;intdp[MAX_N][MAX_S];// 预处理所有 dp[n][s] 的值voidprecompute(){// 初始化：没有数字需要猜的情况for(ints=0;s<MAX_S;++s)dp[0][s]=0;// 初始化：不能承受任何 strike 的情况for(intn=1;n<MAX_N;++n)dp[n][0]=n;// 动态规划递推for(intn=1;n<MAX_N;++n){for(ints=1;s<MAX_S;++s){intbest=INF;// 尝试所有可能的猜测位置 kfor(intk=0;k<n;++k){intstrikePart=dp[k][s-1];// 猜大后的情况intsmilePart=dp[n-k-1][s];// 猜小后的情况intworst=1+max(strikePart,smilePart);if(worst<best)best=worst;}dp[n][s]=best;}}}intmain(){precompute();// 预先计算intc,n,S;cin>>c;while(c--){cin>>n>>S;ints=S-1;// Bob 最多能承受的 strike 次数if(s<0)s=0;// 安全处理边界cout<<dp[n][s]<<endl;}return0;}

样例解析

样例输入

2 3 2 4 1

样例输出

2 4

解释：

1. N = 3 , S = 2 N=3,\ S=2N=3,S=2：Bob \texttt{Bob}Bob最多能承受1 11次strike \texttt{strike}strike。最优策略是先猜1 11：

   • 若得strike \texttt{strike}strike，则X = 0 X=0X=0，下一轮猜0 00，共2 22次。
   • 若得smile \texttt{smile}smile，则X = 2 X=2X=2，下一轮猜2 22，共2 22次。
   • 若猜中，则只需1 11次。
     最坏情况为2 22次。

2. N = 4 , S = 1 N=4,\ S=1N=4,S=1：Bob \texttt{Bob}Bob不能承受任何strike \texttt{strike}strike（s = 0 s=0s=0）。只能从0 00开始顺序猜测，最坏情况（X = 3 X=3X=3）需要猜0 , 1 , 2 , 3 0,1,2,30,1,2,3共4 44次。

总结

本题通过动态规划巧妙地处理了带有strike \texttt{strike}strike限制的猜数策略问题。关键在于定义状态d p [ n ] [ s ] dp[n][s]dp[n][s]并找到正确的状态转移方程，即每次猜测后根据反馈（strike \texttt{strike}strike或smile \texttt{smile}smile）进入不同的子问题。预处理所有状态后，即可快速回答每个测试用例。该算法在给定数据范围内效率良好，是解决此类“最坏情况最优策略”问题的典型方法。