zoj 1503 - One Person "The Price is Right"
來(lái)源:程序員人生 發(fā)布時(shí)間:2014-10-10 08:00:01 閱讀次數(shù):2420次
題目:有一個(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)。
#include <iostream>
#include <cstdlib>
using namespace std;
long long F[ 31 ][ 31 ];
int main()
{
for ( long long i = 0 ; i <= 30 ; ++ i )
F[ i ][ 0 ] = i;
for ( int i = 0 ; i <= 30 ; ++ i )
F[ 0 ][ i ] = 0L;
for ( int i = 1 ; i <= 30 ; ++ i )
for ( int j = 1 ; j <= 30 ; ++ j )
F[ i ][ j ] = F[ i-1 ][ j ]+F[ i-1 ][ j-1 ]+1;
int G,L,C = 1;
while ( cin >> G >> L && ( G || L ) )
cout << "Case " << C++ << ": " << F[ G ][ L ] << endl;
return 0;
}
生活不易,碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)