PKU 1243 One Person
http://poj.org/problem?id=1243
以下のようなルールで数字あてゲームをする。
最初参加者はguessポイントとlifeポイントを持っている。
そして、guessポイントをひとつ消費してある数字が、答えの数字と同じか、それより小さいか、それより大きいかを聞くことができる。
答えと同じであれば参加者が勝利する。
また、答えの数字より大きかった場合lifeポイントをひとつ失う。
ここで、guessポイントを使いきっても正解できなかったり、lifeポイント0の状態で答えの数字より大きい数字を尋ねてしまうと負けになる。
このとき、あるguessポイントGとlifeポイントLで確実に正解できるのは数字の上限が1からいくつまでの時かを答えろというような問題。
あるguessポイントGとlifeポイントLで答えられる数字の個数は
1+(G-1のguessポイントとL-1のlifeポイントで答えられる数字の個数)+(G-1のguessポイントとLのlifeポイントで答えられる数字の個数)で表すことができるということに気づけたので解けました。
ll memo[40][40]; bool vis[40][40]; ll rec(int L,int G){ if(!L)return G; if(G==1)return 1; if(vis[L][G])return memo[L][G]; vis[L][G]=true; return memo[L][G]=1+rec(L,G-1)+rec(L-1,G-1); } main(){ int l,g; int ca=0; while(cin>>g>>l,l|g)printf("Case %d: %lld\n",++ca,rec(l,g)); }