给个题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4513

 

题目大意就是求n的全排列中，把数值看成高度，有多少个排列从左边看能看到l个，从右边能看到r个。

 

我们做一般的排列的题目的时候，往往是通过1-n的答案来递推n+1的答案。。但是本题并不可以这样，，，

因为n+1会把原序列分成两个部分，之后从左边能看见的只能是左边那个部分的加上n+1，右边的类似。。。

 

所以我们考虑计算出1-n的答案之后，把每个元素"长高"1,然后再把1插入进去。这样得到的仍然是一个排列。

而且这样做的好处是，1不会挡住任何比它大的元素，所以只用考虑它能不能被看见即可。

1插在最左端的时候，从左能看到的多了一个，右边不变；1插在最右端的时候相反。

其他情况1都看不见，左右能看到的都不变。。。

 

#include
     
      #define ll long long#define maxn 25using namespace std;ll f[25][25][25];int n,l,r,T;inline void init(){    f[1][1][1]=1;    for(int i=2;i<=20;i++)        for(int j=1;j<=i;j++){            int tp=i+1-j;            for(int k=1;k<=tp;k++){                f[i][j][k]+=f[i-1][j-1][k];                //put 1 in the left of the permutation of 2-n                f[i][j][k]+=f[i-1][j][k-1];                //put 1 in the right of the permutation of 2-n                f[i][j][k]+=f[i-1][j][k]*(ll)(i-2);                //put 1 in the middle of the permutation of 2-n            }        }}int main(){    init();    scanf("%d",&T);    while(T--){        scanf("%d%d%d",&n,&l,&r);        printf("%lld\n",f[n][l][r]);    }        return 0;}