如何用动态规划解决UVALive6486Skyscrapers长尾词问题？

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

题目：给定N个格子排列成一排，每个格子中填上1到N的数（每个数只能填一次），分别代表每个格子的高度。现在给出两个数left和right，分别表示从左向右看和从右向左看，能看到的高度序列。请找出并输出能看到的高度序列。

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

题意：

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

数据范围： N<5000；

思路：

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

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

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

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