《11061PlayingWar》由会员分享,可在线阅读,更多相关《11061PlayingWar(8页珍藏版)》请在金锄头文库上搜索。
1、11061: Playing War nn題組:Problem Set Archive with Online Judgen題號: 11061: Playing Warn陳盈村n解題日期:200814日n題意:在此遊戲中,有一類玩家一旦開始攻擊,就會不停攻擊同一對手,直到全滅對方或無法再攻擊為止。題目要求算出,當防禦方有X (1=X= 3(x,1) = 225/1296 (x-1 , 1) (x,2) = 979/7776 (x-2 , 2) + 1071/1296 (x , 0) + 1981/7776 (x-1 , 1) + 4816/7776 (x , 0)4Y = 3(1,3) = 8
2、55/1296 (0,3) (2,3) = 2890/7776 (0,3) + 441/1296 (1,2) + 2611/7776 (1,2) + 2275/7776 (2,1)X=3,Y=3(X,Y) = 6420/46656 (X-3, Y) + 10017/46656 (X-2 ,Y-1) + 12348/46656 (X-1 ,Y-2) + 17871/46656 (X ,Y-3)5使用Dynamic Programming,最後再查表找出,守方X人,攻方機率剛好0.5的人數。依序求值依序求值1234566n解法範例:例如求例如求(5,5)即為這四個相加即為這四個相加7n討論:(1) 計算量 = 1,000* 2000,用暴力法計算之。O(n2)(2) 攻方有一名士兵留守,最後再加上即可。(3)查表時可採用binary search。8