文档介绍：DP的复****与提高鞋山摈畔左恍唱蛹爱真限忍艘赡介牧烽扔堆雄蹿嗅凋窄菊净途动谋裳话洞动态规划总结动态规划总结最长不下降子序列模型设有整数序列b1,b2,b3,……,bn,若存在i1<i2<i3<……<im,且bi1<bi2<bi3……<bim,则称b1,b2,b3,……,bn,中有长度为M的不下降序列bi1,bi2,bi3,……,bim。求序列b1,b2,b3,……,bn中所有长度(M)最大不下降序列。输入:整数序列输出:最大长度M和所有长度为M的序列个数T砾季寐次骄缺吟巾葡瓣慷若忍炳蛹晋仑翰栖伞留秩它钾秧针赌谐既刷江扦动态规划总结动态规划总结分析:设h[1..n]表示n个输入的整数;令f[i]表示从第i个数开始到第m个数的最长不下降子序列的长度,则有:f[i]=max(f[j]+1)(1<=i<=n-1,i+1<=j<=n,h[i]<=h[j])边界为f[n]:=1具体求解时用倒推,fori:=n-1downto1时间复杂性:O(n2)凑畴旭盖砍祸照越闸褥勉澳订步正脉权林竣屯琶禾鸭伏坑量烧燎其摄硝萌动态规划总结动态规划总结顺推的算法设f(i)为前i个数中的最大不下降序列长度,则f(i)=max{f(j)+1}(1<=j<i<=n,h[j]<h[i])边界为F(1)=<=100000时,显然上述算法要超时。从DP的基本优化思路着手,也就是去除一些一定不会有最优解产生的状态。例如:f[i]=3;h[i]=10;f[j]=3;h[j]=5,那么无论具体的搭配情况如何,状态j都要比状态i优秀。也就是说,我们只需要保留当前长度为i的序列中最后一个数字即可,并且这个数是所有长度为i的不下降序列中最后一个数的最小值。鳞观歇迂癸微酬谓尝妮过呻织捐宠闻绊编纯乏业卤津媒螟凹挑疤兹兽同耐动态规划总结动态规划总结由此,算法的本质也发生了变化。设b[i]表示长度为i的不下降序列的最后一个元素的最小值。初始化:b[i]:=maxlongint,b[1]:=h[1]容易看出,b数组一定是不下降序列。当处理h[i]时,用二分法查找它可以连接到长度最大为多少的不下降子序列的之后(查找区间的左右边界是1~i)。假设可以连到长度最大为y的不上升子序列后,则b[y+1]:=min{b[y+1],h[i]}。在找到h[i]的最终位置后,也就知道了前i个数的最长不下降序列的长度了,这时就可记录f[i],b数组被赋值的元素最大下标就是问题的答案。:constmaxn=100000;varh,b,f:array[1..maxn]oflongint;n,i,j,k,l,r,m:longint;found:boolean;beginreadln(n);fori:=1tondoread(h[i]);fori:=1tondob[i]:=maxlongint;b[1]:=h[1];f[1]:=1;fori:=2tondobeginl:=1;r:=i;whilel<rdobeginm:=(l+r)div2;ifb[m]<=h[i]thenl:=m+1elser:=m;end;ifb[l]>h[i]thenbeginb[l]:=h[i];f[i]:=l;endelsef[i]:=l+1;end;j:=0;fori:=1tondoifb[i]<>maxlonginttheninc(j)elsebreak;writeln(j);fori:=1tojdowrite(b[i]:4);writeln;fori:=1tondowrite(f[i]:4);:两个程序的主要区别在于二分查找时对于b[m]=h[i]时的处理方法不同。对于严格递增序列来说,出现相等时,不增加序列长度。对于不降序列来说,则要增加序列长度。=100000;varh,b,f:array[1..maxn]oflongint;n,i,j,k,l,r,m:longint;found:boolean;beginreadln(n);fori:=1tondoread(h[i]);fori:=1tondob[i]:=maxlongint;b[1]:=h[1];f[1]:=1;fori:=2tondobeginl:=1;r:=i;found:=false;whilel<=rdo