zoj 1503 - One Person "The Price is Right"

題目：有一個(gè)數(shù)字讓你猜，你有k次機(jī)會(huì)，并且有k個(gè)保險(xiǎn)如果猜的低了會(huì)高度你低了，

            高了會(huì)告訴你高了，并且失去一k保險(xiǎn)（k=0時(shí)猜高了就會(huì)失敗），現(xiàn)在問(wèn)你能猜的數(shù)字范圍。

分析：dp，二維動(dòng)態(tài)規(guī)劃。按保險(xiǎn)k和猜的機(jī)會(huì)n遞增的方向dp。

            狀態(tài)：f（G，L）為有G次猜的機(jī)會(huì)，L個(gè)保險(xiǎn)時(shí)確定的數(shù)字范圍（1~N）；

            轉(zhuǎn)移方程：F（G，L）= G（G-1，L）+ 1 + F（G-1，L-1）{ 猜低 + 猜中 + 猜高 }；

            邊界條件：如果沒(méi)有失敗機(jī)會(huì)的話，只能從1開(kāi)始向后猜；

說(shuō)明：（2011-10-03 16:32）。

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)