【Link】:

【Description】

等價題意:
某人在1..n內選一個數x;
然后讓你去猜;
你可以問他是不是在哪個范圍里;
每次會告訴你YES或者NO;
問你在最壞的情況下猜出答案需要猜多少次;
且猜的數字大于x的次數不能超過k次.

【Solution】

動態規劃.
設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]這一段也能用剩下的實驗次數得到.

【NumberOf WA】

1

【Reviw】

用數學的遞推,取代感性的認知.
對問題有了更深的理解。

【Code】

#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\n",i);sol = true;break;}if (!sol) puts("More than 63 trials needed.");}return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7626181.html

總結

以上是生活随笔為你收集整理的【Uva 10934】Dropping water balloons的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。