《最长不下降子序列》由会员分享，可在线阅读，更多相关《最长不下降子序列（27页珍藏版）》请在金锄头文库上搜索。
1、动态规划最最长长不下降子序列不下降子序列无序的序列a1,a2,.,am找到一个最长的序列，满足aiaj.ak;且ijk求出其中最长的非降子序列长度5 2 8 6 3 6 9 745 2 8 6 3 6 9 7 i 以ai结尾的最长非降子序列的长度 = maxk + 1, 0 , =bk，即ai大于长度为K的序列中的最后一个元素，这样就可以使序列的长度增加1，即K=K+1,然后现在的bk=ai2.如果aibk，那么就在b1.bk中找到最大的j,使得bjai,然后因为bjai，所以ai大于长度为j的序列的最后一个元素，那么就可以更新长度为j+1的序列的最后一个元素，即bj+1=ai12345 2
2、8 6 3 6 9 7123455 2 8 6 3 6 9 7123425 2 8 6 3 6 9 71234285 2 8 6 3 6 9 71234265 2 8 6 3 6 9 71234235 2 8 6 3 6 9 712342365 2 8 6 3 6 9 7123423695 2 8 6 3 6 9 7123423675 2 8 6 3 6 9 7拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。区间问题区间问题1.每个状态表示一个区间的局部最优解2.fi, j表示i, j上的“答案”3.多以“线段”形式出现石子归并一条线上N堆石子，分别有各自的重量每次挑选相邻两堆合并起来，代价为他们的重量之和总共合并N-1次，最终变为一堆fij = min (fik + fk+1j + sumij)中间的每一堆石子都能原来的区间合并而成并且一旦合并就不会被拆散可以用前述的fi,j型状态背包问题谢谢
