UVa 1638 Pole Arrangement (递推或DP)

题意：有高为1，2，3...n的杆子各一根排成一行，从左边能看到L根，从右边能看到R根，求杆子的排列有多少种可能。

析：设d（i, j, k）表示高度为1-i的杆子排成一行，从左边看到j根，从右边看到k根的数目。当i>1时，我们按照从大到小的顺序按排杆子，

假设已经安排完i-1根了，那么还剩下一根就是高度为1的了，那么它放在哪都不会挡住任何一根杆子。情况有3种：

1.放在左边，那么在左边一定能够看到它，在右边看不到（因为i>1）；

2.放在右边，那么在右边一定能够看到它，在左边看不到（因为i>1）；

3.剩下的也就是放在中间了，那么我们有多少个地方可以放呢，答案很明显，i-2个，在左右两边都看不到它。

情况1时，在高度在2-i的杆子中，在左边能看到j-1根，从右边能看到k根，因为在左边加上第一根正好是j根，

同理，情况2，在高度在2-i的杆子中，在左边能看到j根，从右边能看到k-1根，因为在右边加上第一根正好是k根，

情况3呢？更好说，在高度在2-i的杆子中，在左边能看到j根，从右边能看到k根，因为在左边和右边都看不到第一根。

综上分析：d（i, j, k) = d(i-1, j-1, k) + d(i-1, j, k-1) + d(i-1, j, k) * (i-2)，边界为d(1, 1 ,1) = 1;

可先把所以情况先扫出来，到时直接查询就行了，快捷方便。注意超过int了，要用long long存储。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#define mod %10056

using namespace std;

typedef long long LL;

LL d[25][25][25];

void init(){

    memset(d, 0, sizeof(d));

    d[1][1][1] = 1;

    for(int i = 2; i <= 20; ++i)

        for(int j = 1; j <= 20; ++j)

            for(int k = 1; k <= 20; ++k)

                d[i][j][k] = d[i-1][j-1][k] + d[i-1][j][k-1] + d[i-1][j][k] * (i-2);

}

int main(){

    init();

    int T, n, l, r;  cin >> T;

    while(T--){

        scanf("%d %d %d", &n, &l, &r);

        printf("%lld\n", d[n][l][r]);

    }

    return 0;

}