UVALive6486如何运用动态规划解决摩天大楼问题？

本文共计995个文字，预计阅读时间需要4分钟。

题目：给定N个格子和一个规则，请填充1到N的数字，每个数字只能使用一次，并分别表示从左到右和从右到左的每个格子的数字。

题意：有N个格子排成一排，在每个格子里填上1到N的数(每个只能填一次)，分别代表每个格子的高度。现在给你两个数left和right，分别表示从左往右看，和从右往左看，能看到的格

题意：

　　有N个格子排成一排，在每个格子里填上1到N的数(每个只能填一次)，分别代表每个格子的高度。现在给你两个数left和right，分别表示从左往右看，和从右往左看，能看到的格子数。问有多少种情况。

数据范围： N<5000；

思路：

　　首先枚举最高的一块，在最高的格子的后面的格子都一定会被挡住。所以，除了最高的那一格之外，从左边能看到的格子，从右边一定看不到；从右边能看到的也是一样。

　　因此，除了最高的那个格子，左边的是否能被看见，和右边的无关。所以，我们可以以最高的格子为界，把这一排格子分成左右两部分。

　　在这样子，我们就可以把左边和右边看成是一种情况：把n个高度不等的方块排成一列，要求从前面只能看到k个，有多少种。

　　　　我们把上面问题（n个格子，看见k个）的结果记为f[n, k]。

　　　　对于上面那个问题，我们考虑两种情况：最高的放在最后，和最高的不放在最后。

　　1. 如果最高的放最后，因为最高的一定不会被挡住，所以，前面n-1个格子，需要被看见k-1个。