#23856: 解題思路
tzuchunchen1015@gmail.com
(TCC)
學校
:
臺北市立第一女子高級中學
編號 : 93686
來源 : [140.112.217.12]
最後登入時間 ：
2024-08-04 20:23:59
可以用 DP 解
維護 K 個球 N 次能夠測試的最大高度
試想我第一次要放在哪個樓層會能夠維持最小
假設放在現在有 K 個球，然後我要維持總共在 N 次解決
那假設我現在把第一次放在第 A 層樓
那我知道如果這一次爆了那我知道 （ K - 1 個球和 N - 1 次能夠達到的最大高度） 就要是 A - 1
（因為放在第 A 層樓用掉第一次）
如果沒爆我還可以往上（ K 個球和 N - 1 次能夠達到的最大高度）
因此轉移式就是 dp[k][n] = (dp[k-1][n-1]+1)+dp[k][n-1]
#42013: Re: 解題思路
kk20180820@gmail.com
(Wayne Yang)
學校
:
國立鳳山高級中學
編號 : 172018
來源 : [39.14.24.86]
最後登入時間 ：
2024-09-14 00:24:32
這裡貼個表格輔助
| n=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| k=0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 2 | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 |
| 3 | 0 | 1 | 3 | 7 | 14 | 25 | 41 | 63 | 92 |
| 4 | 0 | 1 | 3 | 7 | 15 | 30 | 56 | 98 | 162 |
| 5 | 0 | 1 | 3 | 7 | 15 | 31 | 62 | 119 | 218 |
| 6 | 0 | 1 | 3 | 7 | 15 | 31 | 63 | 126 | 246 |
| 7 | 0 | 1 | 3 | 7 | 15 | 31 | 63 | 127 | 254 |
| 8 | 0 | 1 | 3 | 7 | 15 | 31 | 63 | 127 | 255 |
#42015: Re: 解題思路
kk20180820@gmail.com
(Wayne Yang)
學校
:
國立鳳山高級中學
編號 : 172018
來源 : [39.14.24.86]
最後登入時間 ：
2024-09-14 00:24:32
從表格可以發現當施測次數開始>=水球數時，最大樓層就固定了，這是因為在只施測一定次數的限制下，為求保險起見，只能從固定的樓層開始施測。
#42016: Re: 解題思路
kk20180820@gmail.com
(Wayne Yang)
學校
:
國立鳳山高級中學
編號 : 172018
來源 : [39.14.24.86]
最後登入時間 ：
2024-09-14 00:24:32
從表格可以發現當施測次數開始>=水球數時，最大樓層就固定了，這是因為在只施測一定次數的限制下，為求保險起見，只能從固定的樓層開始施測。
打錯了，是 施測次數<=水球數
ZeroJudge Forum