1243 One Person
問題概要
物の値段を当てる次のようなゲームがある。
プレイヤーは値段を言い、
- 当たっていたら勝利
- 外れていたらGが1減る。本当の値段がより低かったか、より高かったかが教えられる。
- 本当の値段がより低かった場合更にLが1減る
GまたはLが0になるとゲームオーバーである。
G,Lが与えられたとき、値段が1〜Nのどの整数でも言い当てられるような最大のNを求めよ。
G,L≦30を満たす。
解法
dp[g][l]にGが残りg,Lが残りlのときに当てられる"値段の幅"であるとする。
このとき、値段としてxを宣言したとする。
当たる場合、実際の値段はもっと小さかった場合、大きかった場合がある。
小さかった場合、G=g-1,L=l-1で1〜x-1の区間にある値段を当てる必要がある。
大きかった場合、x+1〜x+dp[g-1][l]の値段を当てられる。
以上より、dp[g][l]=dp[g-1][l-1]+1+dp[g-1][l]の漸化式が立つ。
ソースコード
int g,l; ll dp[31][31]; int main() { for(int i=1;i<31;i++)rep(j,31) { dp[i][j]=(j>0?dp[i-1][j-1]:0)+dp[i-1][j]+1; } int cs=0; while(scanf("%d%d",&g,&l),g) { printf("Case %d: %lld\n",++cs,dp[g][l]); } return 0; }