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) = 855/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