Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

zz思路

Posted by Victordu at 2008-09-10 17:29:09 on Problem 3088
f[i][j]:走完前i个数,并且有j个combination.
    那么第i+1个数,我们有两个选择,即,要或者不要.
    1.不要.
      那么f[i+1][j]+=f[i][j];即可.
    2.要
      如果要,又可以分为两种情况
      A.将i+1放到这j个combination中的一个去.显然有j种放法.
        故f[i+1][j]+=f[i][j]*j;
        *于是*:f[i+1][j]+=f[i][j]*j+f[i][j];
      B.将i+1独自地作为一个combination插进去,由于之前有j个
        combination,所以有j+1个空隙可以插,于是乎:
        f[i+1][j+1]+=(j+1)*f[i][j];

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator