1. 题目
3. 魅力花园
（park.pas/c/cpp）
【问题描述】
在城市里会有很多花园，我们如何判断某一个花园是不是魅力花园呢？不同的人有不同的要求，而且花园对于不同的人的要求的敏感程度不同。比如市长的要求要比市民的要求有用的多，城管的要求又高于市长的要求。花园的园长很为难。他必须让尽可能多的人都感到满意。
假设有n个群体对花园提出了n个要求，每个群体的要求不同，园长根据要求被提出的时间先后和要求的价值大小进行选择性的满足。园长只会对时间早的和价值高的要求进行满足。例如两个要求A和B的提出时间分别是a，b（a<b），价值分别是a'，b'（a'>b'），那么他们可以同时被满足。
园长为了打造魅力花园，当然希望满足尽可能多的不同群体的要求。他想让你帮他设计一个规划，计算出最多能满足多少个群体的要求。
【输入格式】
第一行一个n，表示有n个群体；
第二行n个整数，n个群体的问题的时间由早到晚排序后的标号顺序；
第三行n个整数，n个群体的问题的价值从大到小排序后的标号顺序；
【输出格式】
一个数表示最多能满足的要求数；
【输入样例】
5
1 4 2 5 3
1 2 4 5 3
【输出样例】
3
【数据范围】
30%的数据：1<=n<=1000;
100%的数据：1<=n<=100000;
2. 算法
最长公共子序列的数据放大版。
方法一：将第一个串中的编号对应到第二个串的坐标记录下来，然后求他的最长不下降子序列。
方法二：本人没学会，参考论文《1D/1D动态规划优化初步》，此处提供代码。
3. 注意事项
如果你想骗分，就照着三个点拿，别优化成退化了。
4. 代码
最长不下降子序列 （Dsqwwe）
program dsqwwe;
var
a,q,p,h:array[0..200000] of longint;
n,i,aa,len,l,r,mid,temp:longint;
begin
assign(input,'park.in');
reset(input);
assign(output,'park.out');
rewrite(output);
readln(n);
for i:=1 to n do
read(h[i]);
for i:=1 to n do
begin
read(aa);
p[aa]:=n-i+1;
end;
for i:=1 to n do
a[i]:=p[h[i]];
len:=0;
q[0]:=maxlongint;
for i:=1 to n do
begin
temp:=0;
l:=0; r:=len;
while (l<=r) do
begin
mid:=(l+r) div 2;
if a[i]<q[mid] then
begin
temp:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
if temp=len then
begin
inc(len);
q[len]:=a[i]
end
else q[temp+1]:=a[i];
end;
writeln(len);
close(input);
close(output);
end.
我不会的那个 (Ray)
program lonely;
type
rec=record
l,r:longint;
end;
var
t,z,i,n,l,r,mid,max:longint;
f:array[0..100010] of rec;
a,x,b:array[0..100010] of longint;
begin
assign(input,'park.in');
reset(input);
assign(output,'park.out');
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do
begin
read(b[i]);
x[b[i]]:=i;
end;
f[0].l:=1;f[0].r:=n;
max:=0;
for z:=1 to n do
begin
i:=x[a[z]];
l:=0;r:=max;
while l<=r do
begin
mid:=(l+r)>>1;
if f[mid].r<i then l:=mid+1;
if f[mid].l>i then r:=mid-1;
if (f[mid].l<=i)and(f[mid].r>=i) then break;
end;
t:=mid;
if t+1>max then
begin
max:=t+1;
f[max].l:=i;
f[max].r:=n;
f[t].r:=i-1;
end
else
begin
f[t+1].l:=i;
f[t].r:=i-1;
end;
end;
writeln(max);
close(input);
close(output);
end.