线性动态规划(2)

第1行有1个正整数n(1<=n<=300)，表示给定的平面上的点数。接下来的n行中，每行2个实数，分别表示点的x坐标和y坐标。 [输出数据]

将计算的最短双调TSP回路的长度（保留2位小数）输出到文件。 知其然：

按横坐标排序。

设F[I,J]表示分两条支路，一条到达i点，另一条到达j点的最小值。I

f[i-1,i]:=min(f[i-1,i],f[j,i-1]+dis(j,i)); 知其所以然：

之所以是线性dp，因为第i个点可以交接在第1到i-1个点上。由于f[I,j]=f[j,i]，所以规定i<=j;

评价：由《红包》那题联想出，如果能将点逆时针或顺时针排序，就好办。但实际不用。 思考：排序解决后效性 延伸： 代码： type

bb=array[1..2] of real; var

a:array[0..300] of bb;

f:array[0..300,0..300] of real; n:longint;

procedure sort(l,r:longint); var

m:bb;

mid1,mid2:real; i,j:longint; begin

i:=l;j:=r;mid1:=a[(l+r) shr 1,1];mid2:=a[(l+r) shr 1,2]; repeat

while (a[i,1]mid1)or((a[j,1]=mid1)and(a[j,2]>mid2)) do j:=j-1; if i<=j then begin

m:=a[i]; a[i]:=a[j]; a[j]:=m; inc(i); dec(j); end; until i>=j;

if l

procedure rf;

var

i,j:longint; begin

assign(input,'bitonic.in'); reset(input); readln(n);

for i:=1 to n do readln(a[i,1],a[i,2]); close(input); sort(1,n); end;

function dis(x,y:longint):real; begin

dis:=sqrt(sqr(a[x,1]-a[y,1])+sqr(a[x,2]-a[y,2])); end;

function min(x,y:real):real; begin

if x>y then exit(y) else exit(x); end;

procedure main; var

i,j:longint; begin

fillchar(f,sizeof(f),$7f); f[0,0]:=0;

for i:=1 to n do f[1,i]:=dis(1,i); for i:=2 to n do begin

for j:=1 to i-2 do f[j,i]:=f[j,i-1]+dis(i,i-1);

for j:=1 to i-2 do f[i-1,i]:=min(f[i-1,i],f[j,i-1]+dis(j,i)); end;

f[n-1,n]:=f[n-1,n]+dis(n-1,n); end;

procedure wf; begin

assign(output,'bitonic.out'); rewrite(output);

writeln(trunc(f[n-1,n]*100) div 100,'.',trunc(f[n-1,n]*100) mod 100); close(output); end;

begin rf; main; wf; end.