演出队列解题报告.doc

演出队列解题报告题目描述 今年是镇海中学的百年校庆。校庆演出时，导演需要一列连续的身高递增的学生来演出一个节目。现在有一列连续排列的学生，可以从这些学生中筛选掉最多一段连续的几个学生。然后从剩下的学生中，选出连续的若干个，这些学生的身高依次连续递增。求可以得到的身高连续递增队列的最大长度？输入 输入文件第一行只有一个整数n。 第二行有n个正整数（互相之间以一个空格分隔），表示连续排列的每个学生的身高。输出 输出文件仅有一行，该行只有一个整数，表示符合要求的最长队列的长度。样例输入13176 171 172 173 179 177 178 175 176 177 170 178 179样例输出6提示【样例说明1】 筛选掉第5、6、7三个（179 177 178）后，得到长度最长的连续递增序列：171 172 173 175 176 177【样例输入2】 10176 175 171 172 173 175 176 170 168 158【样例输出2】5【样例说明2】 长度最长的连续递增序列为第3-7个：171 172 173 175 176【数据说明】 30%的数据n2070%的数据n200100%的数据n5000,高度不超过109。本题考察点：动态规划、枚举暴力一开始，看到n5000，心里一直想着用O（nlogn）的算法，但发现很难实现，于是改用O（n2)，心慌慌超时，后来发现，其实算法的复杂度不足o（n2),准确来讲，大约是n（n-1）/2，思路如下： 以样例为例子 首先，我们按照没有删去的，算出fi，fi表示以i结尾的最长上升数列 阶段：一个数为一个阶段 动归三要素： 状态：以i结尾的最长上升数列 转移方程：if ai-1ai then fi:=fi-1+1 else fi:=1; 最后找出f数组中的最大值，存在ans变量里i，j是两个指针，用来枚举删掉的数列，i从2到n-1，表示要删的数列的最左边的数，j从i到n-1，表示要删的数列的最右边的数，很显然，删去最左，最右两个数是毫无意义的，这样不能使最大长度变大，所以也不用考虑，省点时间for i:=2 to n-1 do for j:=i to n-1 do紧接着，我们来思考，为什么要删除一段数： 很显然，删除一段数，是为了让取的数列变长，怎么样才能变长呢？ 只有当删除数列的两端的数ai-1与aj+1满足ai-1=aj+1时，无需考虑那么，如果满足上述条件，我们应该如何处理呢？这里我们以样例来说明如图：当i,j的位置如图所示时，删除的数列为179,177,178，此时发现，满足条件，则计算拼接后的上升数列的长度。由于前面我们已经算过f，所以，fi-1不受删除数列影响，真正影响的是后面，于是，我们开始寻找右边的上升数列的最右边的数，即 k:=j+1; while akak+1 do inc(k);最后找到的k如图所示找到之后，我们把数列拼接起来，重新算出最长上升数列，式子为：k-j+fi-1我们将该式子与ans比较，如果大于ans，存入ans，否则不变以此类推，最后输出ans代码如下（Pascal）：var f,a:array0.5001 of longint;/a保存原数，f保存动归结果 n,i,j,ans,k:longint;begin readln(n); for i:=1 to n do read(ai); readln; f1:=1; for i:=2 to n do if ai-1ai then fi:=fi-1+1 else fi:=1;/动归 ans:=-MAXLONGINT; for i:=1 to n do if ansfi then ans:=fi; for i:=2 to n-1 do for j:=i to n-1 do/枚举开始 if ai-1aj+1 then begin/满足条件 k:=j+1; while akans then an