→ crazyplum:PO到TIOJ的討論區會不會快一點阿@@? 08/09 18:04
→ yuscvscv:目前在比賽啊 會被裱 08/10 01:00
→ crazyplum:可是PO在這裡還是會被強者群看到阿(攤手) 08/10 12:03
→ yuscvscv:可是看到的強者群大多都非參予比賽的啊~ 08/10 13:02
→ xluds24805:因為pA用數學解就是最快的嘛~，代入公式就好了 08/10 22:18
→ yuscvscv:導不出來啊Q Q 08/11 06:45
→ xluds24805:我導出的公式是：(C 3n取n)/(2n+1) 08/11 19:53
→ xluds24805:測試過了，沒問題的~ 08/11 19:54
→ yuscvscv:能不能給一下推導方式呢? 08/11 23:28
推 elevenyeast:快樂營 聽起來好耳熟 08/13 00:38
→ yuscvscv:XD 08/13 01:54
...你確定要聽我的推導方式啊
好吧~
(其實我是有點蒙出來的> <)
首先，先轉化題目
有一個人在原點，遇到帶200元的就往右走，遇到帶600元的就往上走
則總排列數就等於---從原點走捷徑到(2n,n)且不越過(過原點，斜率為0.5的那條線)
接下來穿插一下---
若從原點走捷徑到(n,n)且不越過對角線的話，方法數是(C 2n取n)/(n+1)
因為...
若把所有的路徑提出來，然後把越過對角線後的路徑，
往上走的改成往右走，往右走的改成往上走
則所有越過對角線路徑都會達到(n-1,n+1)
故越過對角線的路徑數為(C 2n取n-1)
而沒越過對角線的路徑數為(C 2n取n)-(C 2n取n-1)=(C 2n取n)/(n+1)
故我推測題目的方法數也是那樣的形式
把(C 3n取n)除以畫圖求出的總排列數，恰得2n+1......求出來了
(推測出)
從原點走捷徑到(xn,n)且不越過(過原點，斜率為(1/x)的那條線)
的總方法數為(C xn取n)/(xn+1)
而越過那條線的線方法數為(C xn取n-1)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.121.78.162
推 yuscvscv:聽起來好像DP 好神妙~~~ 08/13 23:10
→ yuscvscv:話說原PO是學過排列組合嗎? //看起來好像學校的解法 08/13 23:12
→ crazyplum:阿 這的確是排列組合XD 08/14 00:07
→ crazyplum:不過學校的題目都不用導公式，手動DP也能過 08/14 00:07
推 yuscvscv:可是TIOJ Q Q 08/14 03:06