首页 > 代码库 > UVa 1638 (递推) Pole Arrangement
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) //分别对应三种决策
1 #include <cstdio> 2 typedef long long LL; 3 const int maxn = 20; 4 LL f[22][22][22]; 5 6 void Init() 7 { 8 f[1][1][1] = 1; 9 for(int i = 2; i <= maxn; ++i)10 for(int j = 1; j <= i; ++j)11 for(int k = 1; j + k - 1 <= i; ++k)12 f[i][j][k] = f[i-1][j-1][k] + f[i-1][j][k-1] + (i-2)*f[i-1][j][k];13 }14 15 int main()16 {17 Init();18 int T;19 scanf("%d", &T);20 while(T--)21 {22 int n, l, r;23 scanf("%d%d%d", &n, &l, &r);24 printf("%lld\n", f[n][l][r]);25 }26 27 return 0;28 }
UVa 1638 (递推) Pole Arrangement
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。