HDU 4372

题意：有n个建筑高度为1~n，从前看能看到f个，从后看能看到b个，求可能有多少种排序情况。

思路：

五个小时花了3.5小时在上面，结果靠强行yy出了递推式（事后发现。。yy对了95%，跪在各种细节上，比赛结束也没A掉。。

只能说大力出奇迹！但这种奇迹往往会毁在不经意的细节上orz

?

?

分析几组数据我们可以发现，最高的n号楼一定是可以看到的，无论是从左还是右。

那么民那桑，先固定住n号楼的位置，将n号楼左边分为f-1组，右边b-1组，且用每组最高的那个元素代表这一组；

而后我们可以发现楼n的左边，从左到右，组与组之间最高的元素一定是单调递增的！

且每组中的最高元素一定排在该组的最左边，每组中的其它元素可以任意排列（相当于这个组中所有元素的环排列，所谓环排列就是一个元素位置固定其他元素自己动，方案数等于(n-1)!）。

右边同理。

例如：n = 5 , b = 3 , f = 2。

显然n号楼所在位置一定在第3，或第4：XX5XX或XXX5X

当位置在3之时,左边2个元素分成2组，显然符合结论；

当位置在4之时,左边3个元素分成2组，左边可能的情况为：1 32 5X，21 3 5X ，2 31 5X ， 1 42 5X ，21 4 5X ，2 41 5X ，1 43 5X ，31 4 5X ，3 41 5X...

均满足结论（当然这里的X很明显已经求出来了XP

?

故我们可以先把n-1个元素分成f-1+b-1组,每组做环排列，累计方案数即是答案。

?

而个人分成组做环排列的方法数目，我们称之为第一类stirling数

答案：ans(n, f, b) = C[f + b - 2][f - 1] * S[n - 1][f + b - 2];

?

code：

?

/*
* @author Novicer
* language : C++/C
*/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
         
        
       
      
     
    
   
  

?