poj3671

首先容易想到的是LIS,但是n<=30000,所以肯定要优化;

壮哉单调队列又登场了;

然后再找一个最长不上升序列并求两者最大值即可,复杂度O(n logn);

应该说这是解题通法了,但再回头看题目,这道题中,1<=di<=3这个条件没有用

于是很容易想到,还是以最长不下降序列为例:

明显序列结尾元素只有3种可能:以1开头,以2开头,以3开头(全是3);

设d[1],d[2],d[3]代表上述3种可能;

则从后往前,对于当前数t,d[t]=max{d[t],d[k]+1} (t<=k<=3)

则复杂度优化为O(n);

 var d:array[..] of longint;
a:array[..] of integer;
n,i,t,j:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end; begin
readln(n);
for i:= to n do
readln(a[i]);
for i:=n downto do
begin
t:=a[i];
for j:=t to do
d[t]:=max(d[t],d[j]+);
end;
writeln(n-max(d[],d[]));
end.
上一篇:Android 程序目录及UI的简介


下一篇:POJ 2031 prim