等价题意:
某人在1..n内选一个数x;
然后让你去猜;
你可以问他是不是在哪个范围里;
每次会告诉你YES或者NO;
问你在最坏的情况下猜出答案需要猜多少次;
且猜的数字大于x的次数不能超过k次.
动态规划.
设f[i][j]表示前i个水球,做了j次试验;能得到的最大高度;
这里的f[i][j];
指的是,如果问的数字是1..f[i][j],的话,用i个水球都能够通过试验猜到.
(这里的状态f[i][j]中,j>=i也是可行的状态的..)
考虑第一次试验;
假设从高度x落下;
则
1.如果水球破了
则要保证如果问的数字是1..x-1的话,用i-1个球和j-1次试验能猜得到.
那么,x的最大值应该是f[i-1][j-1]+1;
2.如果水球没破
则我们还剩下i个球以及j-1次试验的机会;
而x的最大值只能是f[i-1][j-1]+1
(这里,我们必须也要照顾到球破了的情况才行..因为是最坏情况)
所以,如果在球没破的时候,我们最多能够处理
x+f[i][j-1]也即1..f[i-1][j-1]+1+f[i][j-1]
这样就能得到状态转移方程了;
f[i][j] = f[i-1][j-1]+1+f[i][j-1]
这样如果想的数字在1..f[i][j]这个范围内都能保证猜得到.
然后在f[k][j],j∈[1..63]中找最小的满足f[k][j]>=n的j;
输出就好;
如果没找到,就输出无解;
UPD1
对转移方程的解释:
这里如果球破了的话,1..f[i-1][j-1]能得到;
球没破的话,f[i-1][j-1]+2..f[i][j]这一段也能用剩下的实验次数得到.
1
用数学的递推,取代感性的认知.
对问题有了更深的理解。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 64;
ll f[N+10][N+10],n;
int k;
int main(){
//freopen("F:\rush.txt","r",stdin);
for (int i = 1;i <= 63;i++)
for (int j = 1;j <= 63;j++)
f[i][j] = f[i-1][j-1] + 1 + f[i][j-1];
while (~scanf("%d%lld",&k,&n) && k){
k = min(k,63);
bool sol = false;
for (int i = 1; i <= 63;i++)
if (f[k][i]>=n){
printf("%d
",i);
sol = true;
break;
}
if (!sol) puts("More than 63 trials needed.");
}
return 0;
}