动态规划之最长非升/降子序列
2009-05-10 21:02阅读：
3.难解的问题
（vijos P1369 ）
【描述】在你的帮助下，蔚蓝来到了埃及,在金字塔里，蔚蓝看到了一个问题，传说，能回答出这个
问题的人就能受到埃及法老的祝福，可是蔚蓝日夜奋战，还是想不出来，你能帮帮他么？ 问题是这
样的：
给定一个序列<a1,a2,...,an>.求最长上升子序列(lis)p1<p2<...<pw满足a[p1]<a[p2]<...<a[pw],
例如65 158 170 299 300 155 207 389
LIS=<65,158,170,299,300,389>。
但是，现在还有一个附加条件：求出的最长上升子序列必须含有第K项。比如，在上面的例子中，
要求求出的最长上升子序列必须含有第6项，那么最长上升子序列就是：65 155 207 389。
【输入格式】
第一行是用空格隔开的两个正整数N、K，含义同上所述.
第二行N个数，即给出的序列.
【输出格式】
仅有一个数，表示含有第K项的最长上升子序列的长度.
【时间限制】
各个测试点1s
【注释】
对于60%的数据，N<=10000;
对于100%的数据，1<=n<=300000 ,1<=k<=n,序列的每一个数为小于2^31-1
的非负整数.
【样例输入】
5 3
1 2 3 2 1
【样例输出】
3
【算法分析】
题意要求含有第K项的最长上升子序列，因此分两步求：第K项左边的最长上升子序列、第K项右边的
最长上升子序列。
考虑到数据规模，先作预处理：左边只留下小于第K项的，右边只留下大于第K项的。
为了提高算法效率，设置一个数组b[L]记录长度为L的序列的最后一个数的最大值，因序列是上升序
列，所以该数组是有序的，待处理数X通过二分查找，找到其位置即为相应的长度。（数组元素是各
长度序列的界值（最大或最小），欲求X在序列中的最大长度，只要找到其在数组中的位置）。
【程序实现】
pro
gram p1369;
const mn=300000;
var n,m,k,k2,i,j,max,maxl:longint;
a:array[1..mn] of
longint;
g:array[1..mn,1..2] of
longint; {g[I,1]记录数列，g[I,2]记录最大长度}
b:array[1..2,1..mn] of
longint;
{b[1,L]记录左边的长度为L的序列的最后一个数的最小值,
b[2,L]记录右边的长度为L的序列的最后一个数的最大值}
procedure findh(l,h,x,p,c:longint);{右边的二分查找}
var mid:longint;
begin
if l<h
then begin
mid:=(l+h) div 2;
if x>b[c,mid]
then
findh(l,mid-1,x,p,c)
else if x<b[c,mid]
then findh(mid+1,h,x,p,c)
else g[p,2]:=mid;
end
else begin
if
(x<b[c,l])
then begin
g[p,2]:=l+1;
if
b[c,l+1]<x then b[c,l+1]:=x;
if
l+1>max then max:=l+1;
end
else begin
g[p,2]:=l;b[c,l]:=x end
end;
end;
procedure findl(l,h,x,p,c:longint);{左边的二分查找}
var mid:longint;
begin
if l<h
then begin
mid:=(l+h) div 2;
if x<b[c,mid]
then
findl(l,mid-1,x,p,c)
else if x>b[c,mid]
then findl(mid+1,h,x,p,c)
else g[p,2]:=mid;
end
else begin
if (x>b[c,l])
then begin
g[p,2]:=l+1;
if b[c,l+1]>x
then b[c,l+1]:=x;
if l+1>maxl then
maxl:=l+1;
end
else begin
g[p,2]:=l;b[c,l]:=x end
end;
end;
begin
assign(input,'d1369.txt');
reset(input);
readln(n,k);
for i:=1 to n do
read(a[i]);
m:=0;
for i:=1 to k-1 do
{左边只留下小于a[k]的}
if a[i]<a[k]
then begin inc(m);g[m,1]:=a[i]; end;
inc(m);
k2:=m;
{第K项在新数列中的位置K2}
g[m,1]:=a[k];
for i:=k+1 to n do
{右边只留下大于a[k]的}
if a[i]>a[k]
then begin inc(m);g[m,1]:=a[i]; end;
{从右端开始}
for i:=k2 to m do
b[2,m-i+1]:=0;
{清零}
b[2,1]:=g[m,1];g[m,2]:=1;
max:=1;
for i:=m-1 downto k2 do
findh(1,max,g[i,1],i,2);
{max:右端目前最大的长度}
if k2=1
{maxl:左端目前最大的长度}
then maxl:=0
else begin
maxl:=1;
for i:=2 to k2 do
b[1,i]:=maxlongint;
b[1,1]:=g[1,1];g[1,2]:=1;
for i:=2 to k2-1 do
findl(1,maxl,g[i,1],i,1);
end;
writeln(maxl+g[k2,2]);
end.
程序还可以再简化。
4. CoVH之柯南购物
(vijos P1205)
【描述】
话说柯南开完锁后，本想继续往里走，但是却接到一个电话，原来小哀打电话叫柯南去买衣服（寒）
柯南来到步行街，发现衣服就如同它的价格一样漂亮（暴寒），柯南自然不想买这么贵的衣服，他想
从买到的衣服总是比上一件便宜，但他又想小哀开心，于是他想尽量买到最多的衣服。你能帮帮他吗
？
注：步行街从头到尾有n件商品，每件商品只有一件，柯南不能回头购买。
【输入格式】
输入第一行是n（1<=n<=3000），表示步行街上里有n件衣服
以下n行是步行街每件商品的价格，按顺序从头到尾。
【输出格式】
输出第一行是柯南能购买的最多的商品数，接着是一个空格，再接着是柯南购买商品的方案数除以
10000的余数。
【样例输入】
12
68
69
54
64
68
64
70
67
78
62
98
87
【样例输出】
4 2
【时间限制】
各个测试点1秒
【注释】
注意：本题的方案数指不同的方案数，即
3
2
2
1
的答案应该是
2 1
而不是
2 2
【算法分析】
本题显然是求最长非升子序列，但同时还需求出不同的方案数，即在求最大长度时，要将长度相同但
价格不同的元素的方案数累加起来。
所以设：a[i].jia:第I件衣服的价格；
A[i].m：买第I件衣服最多可买的件数
A[i].p：买这种件数的最多不同方案数
【程序】
program p1205;
const maxn=5000;
var n,maxl,d,i,j,c:longint;
a:array[1..maxn] of record
jia,m,p:integer;end;
st:array[1..maxn] of integer;
{记录具有相同长度的集合}
top:integer;
function ifok(x:integer):boolean;
{判重}
var i:integer;
begin
i:=1;while (i<=top) and
(x<>st[i]) do inc(i);
if i>top then ifok:=true else
ifok:=false;
end;
begin
assign(input,'d1205b.txt');
reset(input);
read(n);
for i:=1 to n do
begin
read(a[i].jia);
a[i].m:=1;
a[i].p:=1;
end;
close(input);
for i:=n-1 downto 1 do
{求最长非升子序列}
begin
maxl:=0; c:=1;
for j:=i+1 to n do
if (a[j].jia<a[i].jia)
then if
(a[j].m>maxl)
{找最长的长度}
then
begin
maxl:=a[j].m;
d:=j;
c:=a[j].p;
{方案数}
top:=1;
st[top]:=a[j].jia;
end
else if
(a[j].m=maxl)
{长度相同，且价格不同时，累加方案}
then
if
ifok(a[j].jia)
then begin
inc(top);
st[top]:=a[j].jia;
c:=(c+a[j].p) mod 10000;
end;
a[i].m:=maxl+1;
a[i].p:=c;
end;
maxl:=0;
d:=0;
for i:=1 to n do
if a[i].m>maxl
then begin
maxl:=a[i].m;
d:=a[i].p;
top:=1;
st[top]:=a[i].jia;
end
else if (a[i].m=maxl) and
ifok(a[i].jia)
then begin
inc(top);
st[top]:=a[i].jia;
d:=(d+a[i].p) mod 10000;
end;
writeln(maxl,' ',d mod
10000);
end.
5.合唱队形
（Vijos P1098)
a[i].u :i~n的最大下降长度；
a[i].d:1~i的最大上升长度；
找出max{a[i].u+a[i].d-1}(i:1~n)
program p1098;
type at=record
h,u,d:integer;end;
var a:array[1..100] of at;
n:integer;
procedure init;
var i,j,max,min:integer;
begin
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to
n do read(a[i].h);
for i:=1 to
n do
begin
a[i].u:=1;a[i].d:=1;
end;
for i:=n-1
downto 1 do
begin
max:=0;
for j:=i+1 to n do
if (a[j].h<a[i].h) and
(a[j].d>max)
then max:=a[j].d;
a[i].d:=max+1;
end;
for i:=2 to
n do
begin
max:=0;
for j:=1 to i-1 do
if (a[j].h<a[i].h) and
(a[j].u>max)
then max:=a[j].u;
a[i].u:=max+1;
end;
max:=0;
for i:=1 to
n do
if
a[i].u+a[i].d-1>max then max:=a[i].u+a[i].d-1;
writeln(n-max);
end;
begin
init;
end.
