提供使用DP的解法
AC:http://tioj.ck.tp.edu.tw/submissions/2811
令[tex]f(n)[/tex]表示信件數量為N時有幾種放法。根據題目定義,信件K不可以放在第K個信封裡,在這裡以箱子Pos及數字代替。
求[tex]f(n+1)[/tex]
要把第[tex]n+1[/tex]封信放到Pos T有n種方法。
1.令T不可以放在Pos n+1,則可以變成有n個信封不可放於原位的問題,共有[tex]f(n)[/tex]種可能。
2.但是T其實可以放在Pos n+1,即是把T和n+1互換位置,剩下的n-1封信有[tex]f(n-1)[/tex]種方法,要加回去。
總方法數[tex]%3Df%28n+1%29%3Dn%5Ctimes%20%28f%28n%29+f%28n-1%29%29[/tex]
遊客,本帖隱藏的內容需要積分高於 100 才可瀏覽,您當前積分為 0
|