传送门
很容易想出\(O(n^3m)\)的方程，三维分别表示某个快递员现在在哪里，然后直接递推即可
然而这样会T，考虑怎么优化。我们发现每一天的时候都有一个快递员的位置是确定的，即在前一天要到的位置。那么我们只要枚举剩下的两个人分别在哪里就行了，复杂度变为\(O(n^2m)\)
//minamoto#include<bits/stdc++.h>#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)#define go(u) for(register int i=head[u],v=ver[i];i;i=Next[i],v=ver[i])#define inf 0x3f3f3f3fusing namespace std;template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}const int N=205,M=1005;int G[N][N],dp[2][N][N],a[M],n,m,ans=inf;int main(){// ?freopen("testdata.in","r",stdin);// ?freopen("express.in","r",stdin);// ?freopen("express.out","w",stdout); ???scanf("%d",&m); ???fp(i,1,m)fp(j,1,m)scanf("%d",&G[i][j]); ???while(~scanf("%d",&a[++n]));--n; ???fp(i,1,m)fp(j,1,m)dp[0][i][j]=inf; ???dp[0][1][2]=0,a[0]=3; ???fp(t,0,n-1){ ???????int p=t&1; ???????fp(i,1,m)fp(j,1,m)dp[p^1][i][j]=inf; ???????fp(i,1,m)fp(j,1,m)if(dp[p][i][j]!=inf){ ???????????cmin(dp[p^1][a[t]][j],dp[p][i][j]+G[i][a[t+1]]); ???????????cmin(dp[p^1][i][a[t]],dp[p][i][j]+G[j][a[t+1]]); ???????????cmin(dp[p^1][i][j],dp[p][i][j]+G[a[t]][a[t+1]]); ???????} ???} ???fp(i,1,m)fp(j,1,m)cmin(ans,dp[n&1][i][j]); ???printf("%d\n",ans);return 0;}P4046 [JSOI2010]快递服务
原文地址：https://www.cnblogs.com/bztMinamoto/p/10006864.html