UVa 1638 Pole Arrangement【递推】

题意：给出n根高度为1,2,3,---n的杆子，从左边能看到l根，右边能够看到r根，问有多少种可能

看的紫书的思路 先假设已经安排好了高度为2---i的杆子，

那么高度为1的杆子的放置方法有三种情况

放在最左边:从左边看得见，右边看不见

放在最右边：从右边看得见，左边看不见

放在中间，有i-2个空位可以插，左右都看不见

所以可以写出递推关系：

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 unsigned long long d[][][];

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         int n,l,r;

         cin>>n>>l>>r;

         memset(d,,sizeof(d));

         d[][][]=;

         for(int i=;i<=n;i++){

             for(int j=;j<=i;j++){

                 for(int k=;k<=i;k++){

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

                 }

             }

         }

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

     }

     return ;

 }

发现就算理解了递推关系式，边界也想了好久，后来发现只需要d[1][1][1],另外的都置0就可以了

加油------------