点这里查看
讨论 / 求解~（用DP）
Zx.MYS 2008-09-03 06:26:00
点我顶贴 收藏 删除
有谁用动规AC的？
#1 majia5@2008-08-22 19:34:00
回复 删除
套公式拉.还有要用高精度
#2 majia5@2008-08-22 19:45:00
回复 删除
baidu一下就可以找到公式了的说

(m-n+1)*(m+n)! / n!(m+1)!

#3 xiaokeke@2008-08-22 20:42:00
回复 删除
麻烦~~~~~
#4 xiaokeke@2008-08-23 16:25:00
回复 删除
组合数学的应用。
#5 guoshi3@2008-08-23 23:21:00
回复 删除
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
回复 删除
纯粹的数学题。

用组合数学，C(m+n,n)表示从m+n个中选n个不考虑是否穿过的总走法数，C(m+n,n-1)表示从m+n中走时穿过对角线，即至少有一个使得找不出前的情形。

ANS:C(m+n,n)-C(m+n,n-1).

可用对称法解决，《奥赛经典》组合问题。

#7 guoshi3@2008-09-03 06:26:00
回复 删除
那个，为啥C(m+n,n-1)表示从m+n中走时穿过对角线的走法数？
查看更多回复
提交回复