题意：n个数，要求从形成单调不减或单调不增的序列，求最少改变多少个数
用f[i,j]表示第i头牛编号为j时的最小修改次数
因为正反均可，所以做正反两遍取min
转移方程 :
从左到右 ：f[i,j]=min{f[i-1,k] + (a[i] != j)} (k<=j) 边界：f[0,1] = f[0,2] = f[0,3] = f[1,a[1]] =0
从右往左： f[i,j]=min{f[i+1,k] + (a[i] != j)} (j<=j) 边界：f[n+1,1] = f[n+1,2] = f[n+1,3] = f[n,a[n]] =0
var n,t1,t2 :longint; i,j,k :longint; f :array[0..30010,0..3] of longint; a :array[0..30010] of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n); for i:=1 to n do read(a[i]); fillchar(f,sizeof(f),127); f[0,1]:=0; f[0,2]:=0; f[0,3]:=0; f[1,a[1]]:=0; for i:=1 to n do for j:=1 to 3 do begin for k:=1 to j do if a[i]=j then f[i,j]:=min(f[i,j],f[i-1,k]) else f[i,j]:=min(f[i,j],f[i-1,k]+1); end; t1:=min(f[n,1],f[n,2]); t1:=min(t1,f[n,3]); // fillchar(f,sizeof(f),127); f[n+1,1]:=0; f[n+1,2]:=0; f[n+1,3]:=0; f[n,a[n]]:=0; for i:=n downto 1 do for j:=1 to 3 do begin for k:=1 to j do if a[i]=j then f[i,j]:=min(f[i,j],f[i+1,k]) else f[i,j]:=min(f[i,j],f[i+1,k]+1); end; t2:=min(f[1,1],f[1,2]); t2:=min(t2,f[1,3]); writeln(min(t1,t2)); end. ——by Eirlys
