大致题意
有(m)个位置,从位置(p)移动到位置(q)需要花费(c(p,q))的价钱,但并不保证(c(p,q)≠c(q,p))
现在有三个员工,初始位置在(1,2,3)和有(n)个请求，任何时刻只有一名员工可以移动，且不允许同一位置上有 (2) 个以上员工。第 (i) 个请求发生在位置 (p_i),公司必须按照顺序,派一名员工到位置 (p_i)去完成请求
求公司的最小花费。
分析
设(f(i,x,y,z))表示解决完前(i)个请求时,三个员工分别在(x,y,z)处时的最小花费,转移:
(f(i+1,p_{i+1},y,z) = min{f(i,x,y,z)+c(x,p_{i+1})}qquad (p_{i+1}≠y≠z))
(f(i+1,x,p_{i+1},z) = min{f(i,x,y,z)+c(y,p_{i+1})}qquad (x≠p_{i+1}≠z))
(f(i+1,x,y,p_{i+1}) = min{f(i,x,y,z)+c(z,p_{i+1})}qquad (x≠y≠p_{i+1}))
时空复杂度(O(nm^3)),无论是在时间上还是空间上都接受不了
考虑优化:
可以发现,在完成第(i)个任务时,一定有一个人站在(p_i)的位置上,也就是说,这个人的信息是"多余"的,只需要记录另外两个人的位置
设(f(i,x,y))表示解决前(i)个请求时,三个员工分别在(x,y,p_i)时的最小花费,转移:
(f(i+1,p_i,y) = min{f(i,x,y)+c(x,p_{i+1})}qquad (p_i≠y≠p_{i+1}))
(f(i+1,x,y) = min{f(i,x,y)+c(p_i,p_{i+1})}qquad (x≠y≠p_{i+1}))
(f(i+1,x,p_i) = min{f(i,x,y)+c(y,p_{i+1})}qquad (x≠p_i≠p_{i+1}))
时间复杂度(O(nm^2)),再用滚动数组优化一下空间即可
(code)
/*
xcxc82
*/
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9+10
const int MAXN = 210;
int T,L,n;
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;return ~(X-1);
}
int f[2][MAXN][MAXN];
int val[MAXN][MAXN],a[MAXN*5];
int main(){
memset(f,0x3f,sizeof(f));
L = read();
for(int i=1;i<=L;i++){
for(int j=1;j<=L;j++){
val[i][j] = read();
}
}
a[0] = 3;
f[0][1][2] = 0;
int now;
while(cin>>now) a[++n] = now;
for(int i=0;i<=n-1;i++){
memset(f[i+1&1],0x3f,sizeof(f[i+1&1]));
for(int x=1;x<=L;x++){
for(int y=1;y<=L;y++){
if(x==y||x==a[i]||y==a[i]) continue;
f[i+1&1][a[i]][y] = min(f[i+1&1][a[i]][y],f[i&1][x][y]+val[x][a[i+1]]);
f[i+1&1][x][y] = min(f[i+1&1][x][y],f[i&1][x][y]+val[a[i]][a[i+1]]);
f[i+1&1][x][a[i]] = min(f[i+1&1][x][a[i]],f[i&1][x][y]+val[y][a[i+1]]);
}
}
}
int ans = 0x3f3f3f3f;
for(int i=1;i<=L;i++)
for(int j=1;j<=L;j++)
ans = min(ans,f[n&1][i][j]);
printf("%d",ans);
return 0;
}