业务员

· · 个人记录

题目描述

某企业有3位业务员，有M个地址，编号为1~M。 一开始，这3人被分配在地址1、地址2、地址3处。 接下来会有一系列的业务，每个业务即一个地址 对于每个业务的地址，公司要指派3个业务员中的一个赶到那里。 注意同一时刻只有一个业务员在移动，过程中不允许两个业务员地址重叠。 移动花费：从 u 到 v 移动一个业务员，需要花费 w(u,v)。 这个函数不一定对称，即u到v和v到u不一定花费相等，但保证 w(u,u)=0，即停留不动的话不会产生花费。 现在给出总共N个业务，分别为p1~pN，即每个业务的地址。 现在要求按顺序满足所有业务地址，请你输出最小的花费。

输入

第1行有两个整数M,N，分别表示地址数量、业务数量。 第2至M+1行每行包含M个非负整数 第i+1行的第j个数表示w(i,j) （cij<=2000）。 最后一行包含N个整数，表示业务的地址。 一开始3个业务员分别在地址1，2，3。

输出

输出一个整数，表示最小花费。

思路

首先设计一个简单的暴力，dp_{i,j,k,l}表示三个业务员分别在i，j，k时目前执行到第l个业务的最小花费。第四维滚动处理，直接暴力的话空间O(m^3)，时间O(nm^3)

但是其实有花费的dp必定含有上一个业务点，所以枚举时只枚举有上个业务点的状态。时间O(nm^2)。

自带大常数的我TLE了，经过卡常努力，发现其实可以缩成2维，dp_{j,k}表示在第i个业务完成时除了业务点外的两个人在j，k。常数缩小到1/3，速度不知为何快了很多。

为了代码可读性把卡常去掉了。还有别忘记 过程中不允许两个业务员地址重叠，我就是这里调了半天。

code

#include<bits/stdc++.h>
using namespace std;
const int N=410;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int w[N][N],dp[N][N][2],n,m,tmp,last,ans=INT_MAX;
int main(){
    m=read(),n=read();
    for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)w[i][j]=read();
    memset(dp,0x3f,sizeof(dp));dp[2][3][0]=dp[3][2][0]=0;last=1;
    for(int i=1;i<=n;i++){tmp=read();
        for(int j=1;j<=m;j++)for(int k=1;k<=m;k++)dp[j][k][i&1]=0x3f3f3f3f;
        for(int j=1;j<=m;j++)for(int k=1;k<=m;k++)if(j!=k && j!=last && k!=last && j!=tmp && k!=tmp)dp[j][k][i&1]=min(dp[j][k][i&1],dp[j][k][(i-1)&1]+w[last][tmp]);
        for(int j=1;j<=m;j++)for(int k=1;k<=m;k++)if(j!=k && j!=last && k!=last && j!=tmp && last!=tmp)dp[j][last][i&1]=min(dp[j][last][i&1],min(dp[j][k][(i-1)&1],dp[k][j][(i-1)&1])+w[k][tmp]);
        last=tmp;
    }
    for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)ans=min(ans,dp[i][j][n&1]);
    printf("%d\n",ans);
    return 0;
}