演出队列解题报告.doc

《演出队列解题报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《演出队列》解题报告题目描述今年是镇海中学的百年校庆。校庆演出时，导演需要一列连续的身高递增的学生来演出一个节目。现在有一列连续排列的学生，可以从这些学生中筛选掉最多一段连续的几个学生。然后从剩下的学生中，选出连续的若干个，这些学生的身高依次连续递增。求可以得到的身高连续递增队列的最大长度？输入输入文件第一行只有一个整数n。第二行有n个正整数（互相之间以一个空格分隔），表示连续排列的每个学生的身高。输出输出文件仅有一行，该行只有一个整数，表示符合要求的最长队列的长度。样例输入13176171172173179177178

2、175176177170178179样例输出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（

3、nlogn）的算法，但发现很难实现，于是改用O（n^2)，心慌慌超时，后来发现，其实算法的复杂度不足o（n^2),准确来讲，大约是n（n-1）/2，思路如下：以样例为例子首先，我们按照没有删去的，算出f[i]，f[i]表示以i结尾的最长上升数列阶段：一个数为一个阶段动归三要素：状态：以i结尾的最长上升数列转移方程：ifa[i-1]

4、j从i到n-1，表示要删的数列的最右边的数，很显然，删去最左，最右两个数是毫无意义的，这样不能使最大长度变大，所以也不用考虑，省点时间fori:=2ton-1doforj:=iton-1do紧接着，我们来思考，为什么要删除一段数：很显然，删除一段数，是为了让取的数列变长，怎么样才能变长呢？只有当删除数列的两端的数a[i-1]与a[j+1]满足a[i-1]=a[j+1]时，无需考虑那么，如果满足上述条件，我们应该如何处

5、理呢？这里我们以样例来说明如图：当i,j的位置如图所示时，删除的数列为179,177,178，此时发现，满足条件，则计算拼接后的上升数列的长度。由于前面我们已经算过f，所以，f[i-1]不受删除数列影响，真正影响的是后面，于是，我们开始寻找右边的上升数列的最右边的数，即k:=j+1;whilea[k]

6、下（Pascal）：varf,a:array[0..5001]oflongint;//a保存原数，f保存动归结果n,i,j,ans,k:longint;beginreadln(n);fori:=1tondoread(a[i]);readln;f[1]:=1;fori:=2tondoifa[i-1]

7、on-1do//枚举开始ifa[i-1]ansthenans:=k-j+f[i-1];//算出值end;writeln(ans);readlnend.作者：Harry_hcx评测平台：oj.boolen.cn排名第三，欢迎挑战