文档介绍：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
具体求解时用倒推,for i:=n-1 downto 1
时间复杂性:O(n2)
顺推的算法
设f(i)为前i个数中的最大不下降序列长度, 则
f(i)=max{f(j)+1} (1<=j<i<=n, h[j]<h[i])
边界为F(1)=1
下面的优化算法是以顺推方向进行的.
优化
如果当n<=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数组被赋值的元素最大下标就是问题的答案。
在实现时要仔细考虑一些细节情况.
:
const maxn=100000;
var h,b,f:array[1..maxn] of longint;
n,i,j,k,l,r,m:longint;
found :boolean;
begin
readln(n);
for i:=1 to n do read(h[i]);
for i:=1 to n do b[i] := maxlongint;
b[1] := h[1]; f[1] := 1;
for i:=2 to n do begin
l:=1; r:= i;
while l < r do begin
m := (l+r) div 2;
if b[m] <= h[i] then
l := m+1
else r := m;
end;
if b[l] > h[i] then begin
b[l] := h[i];
f[i] := l;
end
else
f[i] := l+1;
end;
j:=0;
for i:=1 to n do
if b[i] <> maxlongint then
inc(j)
else
break;
writeln(j);
for i:=1 to j do
write(b[i]:4);
writeln;
for i:=1 to n do
write(f[i]:4);
end.
数据f存储了以每个元素结尾的最长不下降序列
的长度.
注意:两个程序的主要区别在于二分查找时对于b[m]=h[i]时的处理方法不同。对于严格递增序列来说,出现相等时,不增加序列长度。对于不降序列来说,则要增加序列长度。
2. 求严格递增序列
const maxn=100000;
var h,b,f:array[1..maxn] of longint;
n,i,j,k,l,r,m:longint;
found :boolean;
begin
readln(n);
for i:=1 to n do read(h[i]);
for i:=1 to n do b[i] := maxlongint;
b[1] := h[1]; f[1] := 1;
for i:=2 to n do begin
l:=1; r:= i;
found := false;
while l <= r do begin
m := (l+r) div 2;
if b[m] > h[i