| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
zz思路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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator