#5 guoshi3@2008-08-23 23:21:00
5357
回复
删除
dp的话应当是d[i,j]=d[i-1,j]+d[i,j-1],边界条件是d[i,0]=1(0<=i<=m),d[0,j]=0,(0<j<=n)。
但是这题的数据规模比较大,得用高精度,这样动规从时间和空间上来说都接受不了,还是得推公式。公式应该是c(m+n)(n)-c(m+n)(m+1),但是我也不知道为什么...没推出来呢.....
#6 libojie@2008-09-03 02:50:00
5744
回复
删除
纯粹的数学题。
用组合数学,C(m+n,n)表示从m+n个中选n个不考虑是否穿过的总走法数,C(m+n,n-1)表示从m+n中走时穿过对角线,即至少有一个使得找不出前的情形。
ANS:C(m+n,n)-C(m+n,n-1).
可用对称法解决,《奥赛经典》组合问题。