ACM赛题有n个身高各不相同的人排成一个队列，他们能够互相遮挡，简单的说高身高能挡住低身高的人。现有n个人
ACM赛题
有n个身高各不相同的人排成一个队列，他们能够互相遮挡，简单的说高身高能挡住低身高的人。现有n个人排成一对，要求从前往后看恰好能够看到m个人，从后往前看，恰好能看到r个人。问你给定：n,m,r符合这样队列的有多少排列方式。
[解决办法]
前加后一共可以看到m+r-1个人，那么有n-(m+r-1）个人被遮挡。
这些被遮挡的人可以分布在m+r-2个位置，每个位置并不是只可分布一个人，所以答案是n-(m+r-1)的m+r-2次幂。
求各位大大检查。。信心不足中。。
[解决办法]
个数记为 (n,m,r)，如下：
(n,m,r) = 0 (m<=0 或 r<=0 或 n<m 或 n<r)
= -将最矮的抽出来
(n-1, m, r) -最矮的排在中间某个位置
+ (n-1, m-1, r) -最矮的排在最前
+ (n-1, m, r-1) -最矮的排在最后
[解决办法]
[解决办法]考虑到无论从前看或者从后看，最后看到的一个都是最高的。假设结果为f(n,m,r)，考虑最高人的位置，有递推公式：f(n,m,r)=求和(i从1到n)C(i-1,n-1)f(i,1,r)f(n-i+1,m,1).
而至于f(n,m,1),有递推公式：f(n,m,1)=f(n-1,m-1,1)+(n-2)f(n-1,m,1)。这从考虑最矮人在不在第一位就可以得到。
[解决办法]1、将除了最高的那个人之处分成两个子集C[i] 和 C[j]；
2、C子集的元素个数范围是 [min(m，r), max(m, r) ]，并求出所有子集的组合数（这个容易求)；
3、C子集是有序的，逐个对子集处理，即求出每个子集的固定有序数个数的组合
（求C[i]的 m-1 个的递增子序列的个数，C[i]的 r-1 个的递增子序列的个数）（这个有点难度，个人觉得。但稍微看了下，还是有规律的）；
期待高手指正和补充！！！！！
[解决办法]设f(a,b)为a个不同身高的人排成一队，从前面能看到b个人的不同排法,a<b时f为0
则有递推式：f(a, b)=sum [C(i,a)*f(i,b-1)] i从0到a-1
则题目中的排法数为F(n,m,r)=sum [C(i,n)*f(i,m)*f(n-i-1,r)] i从0到n-1
思路就是找最高的人，从前看从后看都只能看到最高的人，然后把一个问题分解成2个求f的问题
f的公式是递归的，也是根据最高的人的站位i+1来求的，不难理解
问题的关键就是求所有的f，从低往高一个一个推吧，把结果存起来，发挥计算机的优势:)
[解决办法]每次定位最高的那个人
f(n,m,r)=
+_f(n-1,m-1,m-1,n-(m-1),r-1)
+..
+_f(n-1,n-(r-1),m-1,r-1,r-1)
_f(n,mn,m,rn,r)=_f(n,rn,r,mn,m)=
+_f(n,m-1,m-1,rn,r)
+...
+_f(n,mn-1,m-1,rn,r)
+_f(n,mn,m,r-1,r-1)
+...
+_f(n,mn,m,rn-1,r-1)
保存计算过程，空间与时间小于O(n^5)，很麻烦
[解决办法]14楼michael122说的基本正确，方法也很好。
不过，式子应当是：F(n,m,r)=sum [C(i,n-1)*f(i,m)*f(n-i-1,r)] i从0到n-1
f(a, b)=(a-1)*f(a-1,b)+f(a-1,b-1)
边界值：
f(0,0)=1,
a>0, f(a,0)=0.
[解决办法]呵呵，f(a, b)=(a-1)*f(a-1,b)+f(a-1,b-1)，只是和你的考虑方式不一致而已，在组合数学中一个结果，多种表示是很正常的，没有谁对谁错。
类似，按你的考虑方式，f的式子还是应当是：
f(a, b)=sum [C(i,a-1)*f(i,b-1)]
