題意：

2<=L<=200
1<=N<=1000

題解：

一共就三個(gè)員工，我們可以在狀態(tài)中記錄三個(gè)員工的位置；
有：dp[i][x][y][z]:第i個(gè)工作完成后，三個(gè)員工的坐標(biāo)分別是x，y，z，的最小花費(fèi)
轉(zhuǎn)移方程為：
dp[i+1][p[i]][y][z]=min(dp[i][x][y][z]+g[x][p[i+1]])
dp[i+1][x][p[i]][z]=min(dp[i][x][y][z]+g[y][p[i+1]])
dp[i+1][x][y][p[i]]=min(dp[i][x][y][z]+g[z][p[i+1]])
但是：L<=200，這樣開數(shù)組的話，1000 * 200 * 200 * 200，直接爆了，所以不能這么大，我們要考慮節(jié)省空間，看看哪一維可以省略
我們想想，每次完成一個(gè)請(qǐng)求，是不是就應(yīng)該有一個(gè)員工在這個(gè)位置p[i]上，而其他員工不變，所以我們可以用x，y表示本次不執(zhí)行任務(wù)的兩個(gè)員工位置，p[i]為執(zhí)行任務(wù)的員工位置
這樣dp[i][x][y]:第i個(gè)工作完成，未工作的員工位置是x，y，工作的員工位置是p[i],因?yàn)槲覀兪琼樞驁?zhí)行工作，相當(dāng)于對(duì)于i，我們知道p[i-1]的位置，自然就知道上一次三個(gè)人的位置
這樣轉(zhuǎn)移方程為：
dp[i+1][x][y]=min(dp[i+1][x][y],dp[i][x][y]+g[p[i]][p[i+1]]);
dp[i+1][p[i]][y]=min(dp[i+1][p[i]][y],dp[i][x][y]+g[x][p[i+1]]);
dp[i+1][x][p[i]]=min(dp[i+1][x][p[i]],dp[i][x][y]+g[y][p[i+1]]);

代碼：

代碼不知道哪錯(cuò)了。。。

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt","r",stdin);#endif } const int maxn=200; int g[maxn][maxn]; int p[1030]; int dp[1030][maxn][maxn]; int main() {//rd_txt();int l,n;cin>>l>>n;for(int i=1;i<=l;i++){for(int j=1;j<=l;j++){cin>>g[i][j];}}p[0]=3;for(int i=1;i<=n;i++){cin>>p[i];}memset(dp,0x3f,sizeof(dp));dp[0][1][2]=0;for(int i=0;i<n;i++){for(int x=1;x<=l;x++){for(int y=1;y<=l;y++){if(x==y||x==p[i]||y==p[i])continue;dp[i+1][x][y]=min(dp[i+1][x][y],dp[i][x][y]+g[p[i]][p[i+1]]);dp[i+1][p[i]][y]=min(dp[i+1][p[i]][y],dp[i][x][y]+g[x][p[i+1]]);dp[i+1][x][p[i]]=min(dp[i+1][x][p[i]],dp[i][x][y]+g[y][p[i+1]]);} }}int minn=0x3f3f3f3f;for(int i=1;i<=l;i++){for(int j=1;j<=l;j++){if(i==j||i==p[n]||j==p[n])continue;minn=min(minn,dp[n][i][j]);}}cout<<minn;return 0; }

AC代碼：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N = 210, M = 1010, INF = 0x3f3f3f3f;int n, m; int w[N][N]; int f[M][N][N]; int p[M];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )scanf("%d", &w[i][j]);for (int i = 1; i <= m; i ++ ) scanf("%d", &p[i]);p[0] = 3;memset(f, 0x3f, sizeof f);f[0][1][2] = 0;for (int i = 0; i < m; i ++ )for (int x = 1; x <= n; x ++ )for (int y = 1; y <= n; y ++ ){int z = p[i], v = f[i][x][y];if (x == y || x == z || y == z) continue;int u = p[i + 1];f[i + 1][x][y] = min(f[i + 1][x][y], v + w[z][u]);f[i + 1][z][y] = min(f[i + 1][z][y], v + w[x][u]);f[i + 1][x][z] = min(f[i + 1][x][z], v + w[y][u]);}int res = INF;for (int x = 1; x <= n; x ++ )for (int y = 1; y <= n; y ++ ){int z = p[m];if (x == y || x == z || y == z) continue;res = min(res, f[m][x][y]);}printf("%d\n", res);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的AcWing 274. 移动服务的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。