演出队列解题报告.doc

《演出队列》解题报告题目描述今年是镇海中学的百年校庆。校庆演出时,导演需要一列连续的身高递增的学生来演出一个节目。现在有一列连续排列的学生,可以从这些学生中筛选掉最多一段连续的几个学生。然后从剩下的学生中,选出连续的若干个,这些学生的身高依次连续递增。求可以得到的身高连续递增队列的最大长度?输入输入文件第一行只有一个整数n。第二行有n个正整数(互相之间以一个空格分隔),表示连续排列的每个学生的身高。输出输出文件仅有一行,该行只有一个整数,表示符合要求的最长队列的长度。样例输入13176171172173179177178175176177170178179样例输出6提示【样例说明1】筛选掉第5、6、7三个(179177178)后,得到长度最长的连续递增序列:171172173175176177【样例输入2】10176175171172173175176170168158【样例输出2】5【样例说明2】长度最长的连续递增序列为第3-7个:171172173175176【数据说明】30%的数据n≤2070%的数据n≤200100%的数据n≤5000,高度不超过10^9。本题考察点:动态规划、枚举暴力一开始,看到n≤5000,心里一直想着用O(nlogn)的算法,但发现很难实现,于是改用O(n^2),心慌慌超时,后来发现,其实算法的复杂度不足o(n^2),准确来讲,大约是n(n-1)/2,思路如下:以样例为例子首先,我们按照没有删去的,算出f[i],f[i]表示以i结尾的最长上升数列阶段:一个数为一个阶段动归三要素:状态:以i结尾的最长上升数列转移方程:ifa[i-1]<a[i]thenf[i]:=f[i-1]+1elsef[i]:=1;最后找出f数组中的最大值,存在ans变量里i,j是两个指针,用来枚举删掉的数列,i从2到n-1,表示要删的数列的最左边的数,j从i到n-1,表示要删的数列的最右边的数,很显然,删去最左,最右两个数是毫无意义的,这样不能使最大长度变大,所以也不用考虑,省点时间fori:=2ton-1doforj:=iton-1do紧接着,我们来思考,为什么要删除一段数:很显然,删除一段数,是为了让取的数列变长,怎么样才能变长呢?只有当删除数列的两端的数a[i-1]与a[j+1]满足a[i-1]<a[j+1]时,即左右两边的上升数列可以拼成一个数列时,最长上升数列才可能会变大,所以,当a[i-1]>=a[j+1]时,无需考虑那么,如果满足上述条件,我们应该如何处理呢?这里我们以样例来说明如图:当i,j的位置如图所示时,删除的数列为179,177,178,此时发现,满足条件,则计算拼接后的上升数列的长度。由于前面我们已经算过f,所以,f[i-1]不受删除数列影响,真正影响的是后面,于是,我们开始寻找右边的上升数列的最右边的数,即k:=j+1;whilea[k]<a[k+1]doinc(k);最后找到的k如图所示找到之后,我们把数列拼