题目来源：POJ3670

分析

题目大意为：

给定一个长度为N（N<=30000）的仅包含1,2,3的串

求最长不下降子序列（正反均可）

解法

刚开始以为必须用O(N^2)的不下降子序列的经典算法

可是30000的数据不允许

可以发现串中只包含1，2，3三种数字

则在子序列S中，

若 s[i] = 1 则 s[i-1] = 1

s[i] = 2 s[i-1] = 1 or 2

s[i] = 3 s[i-1] = 1 or 2 or 3

可知在源串L中，离L[i]最近的以K(k=1,2,3)结尾的串

必然是最长的以K(K=1,2,3)结尾的串，可以反证

因此F[i]的决策来自于离i最近的F[j]=k(k=1,2,3)

所以 F[I] = MAX { B[K] + 1 ,1<=K<=L[I] }

优化

详解

F[I]表示以L[I]结尾的最长子序列长度，B[K]表示以K结尾的最长子序列长度

细节

每次更新B[K] 记得反过来再做一遍

源程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Program Lwx;
Var 	n:longint;
    	a:array[1..30007] of longint;
    	b:array[1..3] of longint;
    	i, j, k, max:longint;

Begin
	readln(n);
	for i := 1 to n do read(a[i]);
	fillchar(b, sizeof(b), 0);
  	for i := 1 to n do
  	begin
    		k := 0;
    		for j := 1 to a[i] do
    		if b[j] > k then k := b[j];
    		b[a[i]] := k + 1;
  	end;
  	max := 0;
  	for i := 1 to 3 do if b[i] > max then max := b[i];
  	fillchar(b, sizeof(b), 0);
  	for i := n downto 1 do
  	begin
    		k := 0;
    		for j := 1 to a[i] do
    		if b[j] > k then k := b[j];
    		b[a[i]] := k + 1;
  	end;
  	for i := 1 to 3 do if b[i]  >max then max := b[i];
  	write(n - max);
End.