Mobile Service (Standard IO)

題意/Description:

        一個公司有三個移動服務員。如果某個地方有一個請求，某個員工必須趕到那個地方去（那個地方沒有其他員工），某一時刻隻有一個員工能移動。被請求後，他才能移動，不允許在同樣的位置出現兩個員工。從p到q移動一個員工，需要花費c(p,q)。這個函數沒有必要對稱，但是c(p,p)=0。公司必須滿足所有的請求。目标是最小化公司花費。

讀入/Input：

        第一行有兩個整數L,N(3<=L<=200, 1<=N<=1000)。L是位置數；N是請求數。每個位置從1到L編号。下L行每行包含L個非負整數。第i+1行的第j個數表示c(i,j) ，并且它小于2000。最後一行包含N個數，是請求清單。一開始三個服務員分别在位置1，2，3。

輸出/Output：

        一個數M，表示最小服務花費。

題解/solution：

       這是一個dp，這一眼就可以看出。

       但是暴力的dp是會爆空間和時間的。

       是以要改一改。

       首先，要用滾動數組，因為我們的空間不足。

       具體方程見程式。

       還要手動把第一個請求設為初值。

代碼/Code：

var
  n,m,t,min,x:longint;
  b:array [0..4001] of longint;
  a:array [0..201,0..201] of longint;
  f:array [0..1,0..201,0..201] of longint;
function minn(o,p:longint):longint;
begin
  if o<p then exit(o);
  exit(p);
end;

procedure init;
var
  i,j:longint;
begin
  fillchar(f,sizeof(f),$7f div 3);
  readln(n,m);
  for i:=1 to n do
    for j:=1 to n do
      read(a[i,j]);
  for i:=1 to m do
    read(b[i]);
  t:=f[0,0,0];
end;

procedure main;
var
  i,j,k:longint;
begin
  x:=0;
  f[0,1,2]:=a[3,b[1]]; f[0,2,1]:=f[0,1,2];
  f[0,1,3]:=a[2,b[1]]; f[0,3,1]:=f[0,1,3];
  f[0,2,3]:=a[1,b[1]]; f[0,3,2]:=f[0,2,3];
  for k:=2 to m do
    begin
      x:=x xor 1;
      for i:=1 to n do
        for j:=1 to n do
          f[x,i,j]:=t;
      for i:=1 to n do
        for j:=1 to n do
          if (i<>j) and (i<>b[k-1]) and (j<>b[k-1]) then
            begin
              f[x,i,j]:=minn(f[x,i,j],f[x xor 1,i,j]+a[b[k-1],b[k]]);
              f[x,j,i]:=f[x,i,j];
              f[x,b[k-1],j]:=minn(f[x,b[k-1],j],f[x xor 1,i,j]+a[i,b[k]]);
              f[x,j,b[k-1]]:=f[x,b[k-1],j];
              f[x,b[k-1],i]:=minn(f[x,b[k-1],i],f[x xor 1,i,j]+a[j,b[k]]);
              f[x,i,b[k-1]]:=f[x,b[k-1],i];
            end;
    end;
end;

procedure print;
var
  i,j:longint;
begin
  min:=maxlongint;
  for i:=1 to n do
    for j:=1 to n do
      if min>f[x,i,j] then min:=f[x,i,j];
  write(min);
end;

begin
  init;
  main;
  print;
end.