Re: [請益] 好難的題目

看板CSCamp2009作者 (狼)時間16年前 (2009/08/13 20:03), 編輯推噓2(2推 0噓 3→)
留言5則, 2人參與, 最新討論串3/3 (看更多)
-- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.171.138.86
→
08/09 18:04,
PO到TIOJ的討論區會不會快一點阿@@?
08/09 18:04
→
08/10 01:00,
目前在比賽啊 會被裱
08/10 01:00
→
08/10 12:03,
可是PO在這裡還是會被強者群看到阿(攤手)
08/10 12:03
→
08/10 13:02,
可是看到的強者群大多都非參予比賽的啊~
08/10 13:02
→
08/10 22:18,
因為pA用數學解就是最快的嘛~，代入公式就好了
08/10 22:18
→
08/11 06:45,
導不出來啊Q Q
08/11 06:45
→
08/11 19:53,
我導出的公式是：(C 3n取n)/(2n+1)
08/11 19:53
→
08/11 19:54,
測試過了，沒問題的~
08/11 19:54
→
08/11 23:28,
能不能給一下推導方式呢?
08/11 23:28
推
08/13 00:38,
快樂營 聽起來好耳熟
08/13 00:38
→
08/13 01:54,
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
推
08/13 23:10, , 1F
聽起來好像DP 好神妙~~~
08/13 23:10, 1F
→
08/13 23:12, , 2F
話說原PO是學過排列組合嗎? //看起來好像學校的解法
08/13 23:12, 2F
→
08/14 00:07, , 3F
阿 這的確是排列組合XD
08/14 00:07, 3F
→
08/14 00:07, , 4F
不過學校的題目都不用導公式，手動DP也能過
08/14 00:07, 4F
推
08/14 03:06, , 5F
可是TIOJ Q Q
08/14 03:06, 5F
‣ 更多 xluds24805 的文章
文章代碼(AID): #1AX04dyF (CSCamp2009)
‣ 更多 xluds24805 的文章
文章代碼(AID): #1AX04dyF (CSCamp2009)