UVa 1638 (递推) Pole Arrangement

很遗憾，这么好的一道题，自己没想出来，也许太心急了吧。

题意：

有长度为1、2、3...n的n个杆子排成一行。问从左到右看能看到l个杆子，从右往左看能看到r个杆子，有多少种排列方法。

分析：

设状态d(i, j, k)表示i(i≥2)个长度各不相同的杆子，从左往右看能看到j个杆子，从右往左看能看到k个杆子的排列方法。现在假设除了最短的那个杆子，其他i-1个杆子的位置都已排好。那么考虑最短的杆子的位置，有三种决策：

将最短的放到最左边，这样左视图中看到的杆子数加一，右视图不变。
将最短的放到最右边，这样右视图中看到的杆子数加一，左视图不变。
将最短的放在中间，这样从左侧或者从右侧都不会被看到，共有i-2中放法。

因此状态转移方程为：d(i, j, k) = d(i-1, j-1, k) + d(i-1, j, k-1) + (i-2)*d(i-1, j, k) //分别对应三种决策

 #include <cstdio>

 typedef long long LL;

 const int maxn = ;

 LL f[][][];

 void Init()

 {

     f[][][] = ;

     for(int i = ; i <= maxn; ++i)

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

             for(int k = ; j + k -  <= i; ++k)

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

 }

 int main()

 {

     Init();

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n, l, r;

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

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

     }

     return ;

 }

代码君

巴特西

UVa 1638 (递推) Pole Arrangement

最新文章

热门文章